Descriptional Complexity of Formal Systems: 14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012. Proceedings

Description

This book constitutes the refereed proceedings of the 14th International Workshop of Descriptional Complexity of Formal Systems 2012, held in Braga, Portugal, in July 2012. The 20 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 33 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. Front Matter....Pages - Computing with Capsules....Pages 1-19 Minicomplexity....Pages 20-42 Logical Analysis of Hybrid Systems....Pages 43-49 Groups and Automata: A Perfect Match....Pages 50-63 Uniform Distributed Pushdown Automata Systems....Pages 64-75 Removing Nondeterminism in Constant Height Pushdown Automata....Pages 76-88 On Inverse Operations and Their Descriptional Complexity....Pages 89-102 Deciding Representability of Sets of Words of Equal Length....Pages 103-116 Syntactic Complexities of Some Classes of Star-Free Languages....Pages 117-129 Randomness Behaviour in Blum Universal Static Complexity Spaces....Pages 130-140 Production Complexity of Some Operations on Context-Free Languages....Pages 141-154 State Complexity of Star and Square of Union of k Regular Languages....Pages 155-168 State Complexity of Chop Operations on Unary and Finite Languages....Pages 169-182 On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars....Pages 183-195 Descriptional Complexity of Biautomata....Pages 196-208 Descriptional Complexity of Pushdown Store Languages....Pages 209-221 On Internal Contextual Grammars with Subregular Selection Languages....Pages 222-235 An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets....Pages 236-243 Centralized PC Systems of Pushdown Automata versus Multi-head Pushdown Automata....Pages 244-251 State Complexity and Limited Nondeterminism....Pages 252-265 Bounded Counter Languages....Pages 266-279 State Complexity of Projection and Quotient on Unranked Trees....Pages 280-293 Iterating Invertible Binary Transducers....Pages 294-306 Minimal DFA for Symmetric Difference NFA....Pages 307-318 Back Matter....Pages -