Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2011

Descriptional Complexity of Formal Systems

13 International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings

Editors:

  1. Markus Holzer

    1. Institut für Informatik, Universität Giessen, Giessen, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Martin Kutrib

    1. Institut für Informatik, Universität Gießen, Gießen, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Giovanni Pighizzini

    1. Dipartimento di Informatica e Comunicazione, Università degli Studi di Milano, Milano, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Up-to-date results
  • Fast-track conference proceedings
  • State-of-the-art research

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 6808)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): DCFS: International Conference on Descriptional Complexity of Formal Systems

Conference proceedings info: DCFS 2011.

Sections

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (25 papers)

  1. Front Matter

    PDF

  2. Invited Papers

    3. Construction and SAT-Based Verification of Contextual Unfoldings

      • Stefan Schwoon, César Rodríguez
      Pages 34-42

    4. The Power of Diversity

      • Denis Thérien
      Pages 43-54

  3. Regular Papers

    1. Decidability and Shortest Strings in Formal Languages

      • Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey Shallit
      Pages 55-67

    2. On the Degree of Team Cooperation in CD Grammar Systems

      • Fernando Arroyo, Juan Castellanos, Victor Mitrana
      Pages 68-79

    3. The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata

      • Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano
      Pages 80-92

    4. Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages

      • Janusz Brzozowski, Baiyu Li, Yuli Ye
      Pages 93-106

    5. Geometrical Regular Languages and Linear Diophantine Equations

      • Jean-Marc Champarnaud, Jean-Philippe Dubernard, Franck Guingne, Hadrien Jeanne
      Pages 107-120

    7. On Contextual Grammars with Subregular Selection Languages

      • Jürgen Dassow, Florin Manea, Bianca Truthe
      Pages 135-146

    8. Remarks on Separating Words

      • Erik D. Demaine, Sarah Eisenstat, Jeffrey Shallit, David A. Wilson
      Pages 147-157

    10. k-Local Internal Contextual Grammars

      • Radu Gramatovici, Florin Manea
      Pages 172-183

    11. On Synchronized Multitape and Multihead Automata

      • Oscar H. Ibarra, Nicholas Q. Tran
      Pages 184-197

    12. State Complexity of Projected Languages

      • Galina Jirásková, Tomáš Masopust
      Pages 198-211

    13. Note on Reversal of Binary Regular Languages

      • Galina Jirásková, Juraj Šebej
      Pages 212-221

    15. Kleene Theorems for Product Systems

      • Kamal Lodaya, Madhavan Mukund, Ramchandra Phawade
      Pages 235-247
Back to top

Other Volumes

  1. Descriptional Complexity of Formal Systems

Back to top

About this book

This book constitutes the refereed proceedings of the 13th International Workshop of Descriptional Complexity of Formal Systems 2011, held in Limburg, Germany, in July 2011. The 21 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 54 submissions. The topics covered are automata, grammars, languages and related systems, various measures and modes of operations (e.g., determinism and nondeterminism); trade-offs between computational models and/or operations; succinctness of description of (finite) objects; state explosion-like phenomena; circuit complexity of Boolean functions and related measures; resource-bounded or structure-bounded environments; frontiers between decidability and undecidability; universality and reversibility; structural complexity; formal systems for applications (e.g., software reliability, software and hardware testing, modeling of natural languages); nature-motivated (bio-inspired) architectures and unconventional models of computing; Kolmogorov complexity.
Back to top

Keywords

Back to top

Editors and Affiliations

  • Institut für Informatik, Universität Giessen, Giessen, Germany

    Markus Holzer

  • Institut für Informatik, Universität Gießen, Gießen, Germany

    Martin Kutrib

  • Dipartimento di Informatica e Comunicazione, Università degli Studi di Milano, Milano, Italy

    Giovanni Pighizzini

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation