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

✍ Scribed by Jean-Baptiste Jeannin, Dexter Kozen (auth.), Martin Kutrib, Nelma Moreira, Rogério Reis (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2012
• Tongue: English
• Leaves: 329
• Series: Lecture Notes in Computer Science 7386
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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 -

✦ Subjects

Computation by Abstract Devices; Mathematical Logic and Formal Languages; Logics and Meanings of Programs