Descriptional Complexity of Formal Systems

Name: Descriptional Complexity of Formal Systems | 14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012, Proceedings

Martin Kutrib Nelma Moreira Rogério Reis(Herausgeber*in)

Springer (Verlag)

Erschienen am 9. Juli 2012

X, 319 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31623-4 (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 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

Systemvoraussetzungen

Als PDF speichern Als Link merken