Descriptional Complexity of Formal Systems
13 International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings
Published on 18. July 2011
X, 329 pages
978-3-642-22600-7 (ISBN)
Description
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.
More details
Other editions
Additional editions
Markus Holzer | Martin Kutrib | Giovanni Pighizzini
Descriptional Complexity of Formal Systems
13 International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings
Book
07/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Papers
- Linear Algebra Based Bounds for One-Dimensional Cellular Automata
- De Bruijn -Graph Based Bounds
- The Linear Algebra Approach
- Conclusions
- References
- On Restarting Automata with Window Size One
- Introduction
- Restarting Automata
- Restarting Automata with Window Size One
- Nonforgetting Restarting Automata
- CD-Systems of Stateless Deterministic R(1)-Automata
- Extensions and Concluding Remarks
- References
- Construction and SAT-Based Verification of Contextual Unfoldings
- Introduction
- Contextual Nets and Their Unfoldings
- Contextual Nets
- Unfoldings
- Succintness of Contextual vs. Petri Net Unfoldings
- Constructing Contextual Unfoldings
- Verifying Properties about Contextual Nets Using SAT
- References
- The Power of Diversity
- Introduction
- Setting Up the Table
- Boolean Circuits
- Finite Monoids
- Computations in Monoids via Homomorphisms
- The Idea of Counting
- The Idea of Nesting
- Computations in Monoids via Programs
- Conclusion
- References
- Regular Papers
- Decidability and Shortest Strings in Formal Languages
- Introduction
- The First Problem
- The Second Problem
- The Third Problem
- The Fourth Problem
- Conclusions
- References
- On the Degree of Team Cooperation in CD Grammar Systems
- Introduction
- Preliminaries
- Is the Degree of Team Cooperation a Trivial Measure?
- Computability/Decidability Issues
- References
- The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata
- Introduction
- Preliminaries
- Complementing Constant Height dpdas
- Removal of Rejection Policy (ii): Blocking Situation
- Removal of Rejection Policy (iii): Pushdown Overflow/Underflow.
- Removal of Rejection Policy (iv): e-Loop and Mixed-Loop
- Removal of Rejection Policy (iv): Pushdown-Loop
- The Cost of Complementing
- References
- Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages
- Introduction
- Transformations
- Quotient Complexity and Syntactic Complexity
- Prefix-Free Regular Languages
- Suffix-Free Regular Languages
- Bifix-Free Regular Languages
- Conclusions
- References
- Geometrical Regular Languages and Linear Diophantine Equations
- Introduction
- Preliminaries
- Languages, Automata and Graphs
- Geometrical Figures and Their Languages
- Arithmetic
- Strongly Connected Graphs
- Geometry of Strongly Connected Graphs
- Case of Unary Strongly Connected Graphs
- Case of d-Ary Strongly Connected Graphs
- Experimental Study
- Conclusion
- References
- On the Number of Components and Clusters of Non-returning Parallel Communicating Grammar Systems
- Introduction
- Preliminaries and Definitions
- The Number of Components and Clusters
- Unary Languages
- Conclusion
- References
- On Contextual Grammars with Subregular Selection Languages
- Introduction
- Definitions
- Selection with Bounded Resources
- Circular, Ordered, and Union-Free Selection
- References
- Remarks on Separating Words
- Introduction
- Independence of Alphabet Size
- Average Case
- Lower Bounds for Words of Equal Length
- Differences Near the Beginning or End of Words
- Fingerprints
- Pairs with Low Hamming Distance
- Special Classes of Words
- Reversals
- Conjugates
- Nondeterministic Separation
- Separation by 2DPDA's
- Permutation Automata
- References
- State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal
- Introduction
- Preliminaries
- State Complexity of L1*L2
- State Complexity of L1*L2
- State Complexity of L1RL2
- State Complexity of L1RL2
- Conclusion
- References
- k-Local Internal Contextual Grammars
- Introduction
- Preliminaries
- Language Theoretic Properties
- Computational Aspects
- Conclusions
- References
- On Synchronized Multitape and Multihead Automata
- Introduction
- One-Way Multitape NPDAs
- One-Way Multitape DFAs
- Precise Bound on k
- Converting a k-Synchronized n-Tape DFA to a 0-Synchronized n-Tape DFA
- Tightness of the Upper Bound
- Synchronizability of n-Tape DFA/NFA
- Two-Way Multitape NFAs
- Multihead Automata
- One-Way Model
- Two-Way Model
- References
- State Complexity of Projected Languages
- Introduction
- Preliminaries and Definitions
- DFAs as Graphs
- State Complexity of Projected Regular Languages
- State Complexity of Projected Finite Languages
- Conclusion
- References
- Note on Reversal of Binary Regular Languages
- Introduction
- Preliminaries
- Binary Witness Languages for Reversal
- Binary Witnesses for Reversal in Some Other Results
- Conclusions
- References
- State Complexity of Operations n Two-Way Deterministic Finite Automata over a Unary Alphabet
- Introduction
- Unary 2DFAs and Their Expressive Power
- Union and Intersection
- Kleene Star
- Power
- Concatenation
- Summary
- References
- Kleene Theorems for Product Systems
- Introduction
- Labels and Products
- Expressions and Languages
- Sums
- Connected Expressions
- Omega-Power and Shuffle
- From Expressions to Product Automata
- Connected Expressions
- Omega-Power and Shuffle
- FC-Products to Expressions
- Conclusion
- References
- Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals
- Introduction
- Preliminaries and Definitions
- Head Turns on Bounded Languages
- Non-Recursive Trade-Offs
- References
- State Trade-Offs in Unranked Tree Automata
- Introduction
- Preliminaries
- Maximal Trade-Off in DTA(DFA)
- Lower Bound Results
- Results for DTA(NFA)
- Results for NTA(DFA)
- Results for NTA(NFA)
- Conclusion
- References
- A SP2 ? ?P2 Lower Bound Using Mobile Membranes
- Introduction
- Mobile Membranes
- Complexity of Mobile Membranes
- Solving SAT
- Analysis
- Solving 2QBF
- Analysis
- References
- Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity
- Introduction
- Definitions
- A Bound for Recursively Enumerable Languages
- A Bound for Some Other Language Families
- Conclusions
- References
- Transition Function Complexity of Finite Automata
- Introduction
- Preliminaries
- Finite Automata
- Boolean Circuits
- Complexity Classes PSPACE and P/Poly
- Representations of Automata
- BC-Complexity of an Automaton
- Minimization
- Conclusions
- References
- Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences
- Introduction
- Preliminaries
- Crossing Sequences and the Mixing Lemma
- Complexity of Nondeterministic Multitape Computations
- Other Complexity Relations
- Conclusions
- References
- Author Index
