Descriptional Complexity of Formal Systems
14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012, Proceedings
Published on 9. July 2012
X, 319 pages
978-3-642-31623-4 (ISBN)
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.
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.
More details
Other editions
Additional editions
Martin Kutrib | Nelma Moreira | Rogério Reis
Descriptional Complexity of Formal Systems
14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012, Proceedings
Book
07/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Invited Papers
- Computing with Capsules
- Introduction
- Definitions
- Capsules
- Scope, Free and Bound Variables
- Scoping Issues
- The -Calculus
- Dynamic Scoping
- Static Scoping with Closures
- Static Scoping with Capsules
- Soundness
- Evaluation Rules for Capsules
- -Reduction
- Soundness
- Closure Conversion
- A Functional/Imperative Language
- Expressions
- Types
- Evaluation
- Garbage Collection
- Conclusion
- References
- Minicomplexity
- Introduction
- One-Way Automata
- Size Complexity Basics
- More Problems
- Reductions
- Nondeterminism
- Complement and Reversal
- Completeness
- Harder Problems
- Alternation
- Two-Way Automata
- The Sakoda-Sipser Conjecture
- A Stronger Conjecture I
- A Stronger Conjecture II
- Alternation Again
- Relation to Turing Machine Complexity
- Hardness Propagation by Certificates
- Conclusion
- References
- Logical Analysis of Hybrid Systems
- Overview
- Differential Dynamic Logic
- Complete Relations
- Conclusions and Future Work
- References
- Groups and Automata: A Perfect Match
- Introduction
- Free Groups
- Language Theory for Groups
- Stallings Automata
- Hyperbolic Groups
- Automatic Groups
- Automaton Groups
- Automata and Dynamics
- References
- Regular Papers
- Uniform Distributed Pushdown Automata Systems
- Introduction
- Basic Definitions
- Computational Power
- Decidability and Closure Properties
- Final Remarks
- References
- Removing Nondeterminism in Constant Height Pushdown Automata
- Introduction
- Preliminaries
- A Double-Exponential Upper Bound
- A Super-Exponential Lower Bound
- Conclusions and Open Problems
- References
- On Inverse Operations and Their Descriptional Complexity
- Introduction
- Definitions
- Inversion Operations
- Inverse Kleene Star
- Inverse Chop-Star
- Inverse Up and Down
- References
- Deciding Representability of Sets of Words of Equal Length
- Introduction
- Membership of Rep and h-Rep in NP
- Membership of h-Rep in ¶
- Membership of a Subproblem of Rep in ¶
- Conclusion
- References
- Syntactic Complexities of Some Classes of Star-Free Languages
- Introduction
- Preliminaries
- Aperiodic Transformations
- Monotonicity in Transformations, Automata and Languages
- Monotonic Transformations, DFA's and Languages
- Monotonic Partial Transformations and IDFA's
- Nearly Monotonic Transformations and DFA's
- Conclusions
- References
- Randomness Behaviour in Blum Universal Static Complexity Spaces
- Introduction
- Notations
- Relations between Universal Complexities
- Infinite Sequences and Randomness
- Conclusions
- References
- Production Complexity of Some Operations on Context-Free Languages
- Introduction
- Production Complexity of Some Languages
- Behaviour under Operations
- Conclusion
- References
- State Complexity of Star and Square of Union of k Regular Languages
- Introduction
- Preliminaries
- State Complexity of (\bigcup_{i=1}^ k Li)*
- State Complexity of (\bigcup_{i=1} ^k L_i)^ 2
- References
- State Complexity of Chop Operations on Unary and Finite Languages
- Introduction
- Definitions
- Nondeterministic State Complexity
- Deterministic State Complexity
- References
- On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars
- Introduction
- Conjunctive Grammars and Ambiguity
- Grammars over a One-Letter Alphabet
- Encoding into Two Nonterminals
- Construction of Bi-partite Grammars
- Decision Problems for Two-Nonterminal Grammars
- Limitations of Two Nonterminals
- Open Problems
- References
- Descriptional Complexity of Biautomata
- Introduction
- Biautomata
- From Deterministic Automata to Biautomata
- From Nondeterministic Automata to Biautomata
- From Syntactic Monoids to Biautomata
- Final Remarks
- References
- Descriptional Complexity of Pushdown Store Languages
- Introduction
- Preliminaries and Definitions
- Pushdown Store Languages: The General Case
- Pushdown Store Languages for Special Cases
- PDA Which Can Never Pop
- Stateless PDA
- Counter Machine
- Computational Complexity of Decidability Questions
- References
- On Internal Contextual Grammars with Subregular Selection Languages
- Introduction
- Definitions
- Selection with Bounded Resources
- Conclusions and Further Work
- References
- An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets
- Introduction
- Preliminaries and Definitions
- Results
- Concluding Remarks
- References
- Centralized PC Systems of Pushdown Automata versus Multi-head Pushdown Automata
- Introduction
- PC Systems of Pushdown Automata
- Multi-head Pushdown Automata
- An Example Language
- References
- State Complexity and Limited Nondeterminism
- Introduction
- Preliminaries
- Nondeterministic Tree Width
- Characterizations of ftw-NFAs
- Converting Finite Tree Width NFAs to DFAs
- Lower Bounds for the Size of ftw-NFAs
- The State Complexity of Union and Intersection
- Other Language Operations
- Conclusion and Open Problems
- References
- Bounded Counter Languages
- Introduction
- Definitions
- Equivalence of Heads and Counters for Deterministic Machines
- Time-Bounds for Counter Machines
- Speed-Up for Counter Machines on Bounded Input
- Discussion
- References
- State Complexity of Projection and Quotient on Unranked Trees
- Introduction
- Preliminaries
- Projection on Unranked Trees
- Quotient
- Auxiliary Results on String Languages
- Lower Bound Technique
- State Complexity of Projection on Unranked Trees
- Upper Bound for Projection on Unranked Trees
- A Lower Bound Construction
- State Complexity of Quotient Operations
- References
- Iterating Invertible Binary Transducers
- Motivation
- Invertible Transducers
- Transduction Semigroups
- Orbit Equivalence and the Orbit Automaton
- Cycle-Cum-Chord Transducers
- Orbit Rationality
- Knuth Normal Form
- Orbit Geometry and Rationality
- Rational Orbit Relations
- Summary and Open Problems
- References
- Minimal DFA for Symmetric Difference NFA
- Introduction
- Symmetric Difference NFA Definitions
- Properties of Minimal -NFAs
- Atomic and -Atomic -NFAs
- Getting a Minimal DFA by Determinization
- Conclusions and Future Work
- References
- Author Index
