Descriptional Complexity of Formal Systems

Name: Descriptional Complexity of Formal Systems | 13 International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

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

Markus Holzer Martin Kutrib Giovanni Pighizzini(Herausgeber*in)

Springer (Verlag)

Erschienen am 18. Juli 2011

X, 329 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22600-7 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken