Development in Language Theory

Name: Development in Language Theory | 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings

Giancarlo Mauri Alberto Leporati(Herausgeber*in)

Springer (Verlag)

Erschienen am 12. Juli 2011

XIV, 482 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22321-1 (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 Talks
Hunting Redundancies in Strings
Redundancy: A Versatile Notion
Avoiding Repetitions and Repeats
Finding Repetitions
Palindromes in DNA Sequence
References
Some Remarks on Automata Minimality
Introduction
Basic Definitions and Notation
Some Graph-Theoretic Tools
Uniformly Minimal Automata
Never-Minimal Automata
Automata Minimality and Transformation Monoid
References
Growth Properties of Power-Free Languages
Preliminaries
Small Languages: Polynomial Plateau
Big Languages: Quest for Upper Bounds
Finding Growth Rates of FAD-Languages
Building Finite Antidictionaries
Big Languages: Quest for Lower Bounds
Big Languages: Asymptotic Formulas
Extending the Techniques to Related Classes of Languages
References
A Functional Program for Regular Expressions Matching Abstract of Invited Talk
References
State Complexity Research and Approximation
Introduction
Preliminaries
Why Many State Complexity Questions Were Not Studied Earlier
A General Algorithm for State Complexity?
New Approach in State Complexity Research
State Complexity Approximation
Definition of State Complexity Approximation
Some Basic Results on State Complexity Approximation
Approximation without Knowing Actual State Complexity
Future Directions
References
Regular Papers
Counting the Orderings for Multisets in Consecutive Ones Property and PQ-Trees
Introduction
Definitions and Terminology
Counting the Frontiers of a PQ-tree
Construction of the PQ-trees
Properties of the PQ-trees
Reduction from #HAM to #FRONT
Hardness Results for #FMO
Instance Construction
Characterization of the Solutions
Reduction from #HAM to #FMO
References
Avoiding Abelian Powers in Partial Words
Introduction
Avoiding Abelian Powers Greater Than Two
Counting Abelian p-Free Partial Words
Inserting Arbitrarily Many Holes
Conclusion
References
Regular Splicing Languages Must Have a Constant
Introduction
Preliminaries
Path-Automata and Synchronizing Words
Splicing Languages Must Have a Constant
The Main Result
References
The Average Transition Complexity of Glushkov and Partial Derivative Automata
Introduction
Regular Expressions and Automata
The Glushkov Automaton
A New Algorithm for Computing Follow()
Counting the Number of Transitions in the Glushkov Automaton
The Average Number of Transitions in Apos()
The Average Number of Transitions in Apd
Counting the Mergings of Transitions
Comparison with Experimental Results
Conclusions
References
Theory of Átomata
Introduction
Languages, Automata and Equations
The Átomaton of a Regular Language
Atomic Automata
Extension of Brzozowski's Theorem on Minimal DFA's
Conclusions
References
Syntactic Complexity of Ideal and Closed Languages
Introduction
Preliminaries
Basic Properties of Syntactic Complexity
Right Ideals and Prefix-Closed Languages
Left Ideals and Suffix-Closed Languages
Two-Sided Ideals and Factor-Closed Languages
Reversal
Conclusions
References
Generalized One-Unambiguity
Introduction
Preliminaries
One-Unambiguous Languages are Not Closed under Boolean Operators
The Weak One-Unambiguity
Minimization Preserves the Transverse Property
From a Weakly One-Unambiguous Expression to a Linear-Size DFA Satisfying the Transverse Property
From a Minimal Automaton Satisfying the Transverse Property to a Weakly One-Unambiguous Expression
Conclusion
References
Simulations over Two-Dimensional On-Line Tessellation Automata
Introduction
Picture Languages and Tiling Systems
Two-Dimensional On-Line Tessellation Automata
Simulations
Autosimulations
Quotienting 2OTA
The Minimal Simulation-Equivalent 2OTA
How to Compute Simulations
The Case of Backward Simulations
Conclusion and Future Work
References
?-Clearing Restarting Automata and CFL
Introduction
Theoretical Background
Coding
Idea of the Algorithm
Conclusion
References
Enumeration and Decidable Properties of Automatic Sequences
Introduction
Connection with Logic
Enumeration
A New Characterization of k-Regular Sequences
Linear Bounds
Other Numeration Systems
Closing Remarks
References
Languages vs. ?-Languages in Regular Infinite Games
Introduction
Technical Preliminaries
Languages, Automata, Games
Classes of Regular Languages
Winning Strategies in Restricted Weak Games
Winning Strategies in Weak Games
Winning Strategies in Strong Games
Conclusion
References
Solving Word Problems in Group Extensions over Infinite Words
Preliminaries
The Group Extension E(A,G) of G by Infinite Words over A
Group Extensions over A=Z[t ]
Realization of Some HNN-Extensions
References
Abelian Primitive Words
Introduction
Definitions
Non-context-Freeness of AQ
Complexity of AQ
A Linear Time Algorithm for Recognizing AQ
Number of Abelian Primitive Roots
Upper Bound
Lower Bound
Counting Abelian Primitive Words
Equivalence Relations on A-Primitive Words
Conclusions
References
Scattered Context-Free Linear Orderings
Introduction
Linear Orderings
Scattered Context-Free Linear Orderings
Decidability in Exponential Time
References
On Prefix Normal Words
Introduction
The Prefix Normal Form
The Language of Prefix Normal Words
Prefix Normal Words vs. Lyndon Words
The Prefix Normal Equivalence
Conclusion and Open Problems
References
On Non-complete Sets and Restivo's Conjecture
Introduction
The Set Sk
Upper Bound for uwl(Sk)
Lower Bound for uwl(Sk)
Conclusion
References
Self-organization in Cellular Automata: A Particle-Based Approach
Introduction
Definitions
Configurations and Cellular Automata
Measures and Density of Configuration
Limit and -Limit sets
Defects
General Definitions
Interfaces
Dislocations
Dynamics
A Step towards Self-organization
Applications
n-state Cyclic Automaton
Automaton #184
Captive One Sided Cellular Automata
Conclusion
References
Chop Operations and Expressions: Descriptional Complexity Considerations
Introduction
Definitions
State Complexity of Chop Operations
Nondeterministic State Complexity
Deterministic State Complexity
Complexity of Chop Expressions
References
Nodes Connected by Path Languages
Introduction
Preliminaries
Reachability Problems on Labeled Graphs
Relations between Reachability Problems on Labeled Graphs
Reachability of Labeled Graphs and Word Problems of Language Families
Conclusions
References
Characterizing the Regular Languages by Nonforgetting Restarting Automata
Introduction
Nonforgetting Restarting Automata
Characterizing the Regular Languages
Deterministic Nonforgetting R(1)-Automata
Concluding Remarks
References
On Two-Way Transducers
Introduction
Preliminaries
3-Phase Finite-Crossing 2NPCMs
Proofs of the Main Results
Finite-Crossing 2NFTs
References
There Does Not Exist a Minimal Full Trio with Respect to Bounded Context-Free Languages
Introduction
Preliminaries
Full Trios Generated by Almost Regular Bounded Context-Free Languages
Examples and Basic Properties of Languages in CkCk+1, kN+
Simplifying the Structure of Bounded Languages in CkCk+1, kN+
Propagation in the Chain
Closure Properties of the Language Families Ck, kN+
Conclusions
References
Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
Introduction
Two-Way Transformation Semigroups
Monogenic Subsemigroups of TTQ
The Distance Travelled After i Steps
: Moving by f Until Advancing by One Position
Index and Period of the Subsemigroup Generated by f
The Main Theorem and Its Implications
Transformation to Sweeping Automata
Transformation to One-Way Automata
References
Deciding Networks of Evolutionary Processors
Introduction
Basic Definitions
The New Halting Condition and Computability Results
Complete ANEPs
Computational Complexity
References
From Linear Partitions to Parallelogram Polyominoes
Introduction
Preliminaries
The Algorithm
The Data Structure
Complexity
Conclusions
References
On Brzozowski's Conjecture for the FreeBurnside Semigroup Satisfying x^2 = x^3$
Preliminaries
Procedure Ancestor and Primary Series of Words
The Proof of the Main Result
Growth Rates of Congruence Classes
References
Never Minimal Automata and the Rainbow Bipartite Subgraph Problem
Introduction
The Syntactic Graphs
The Rainbow Bipartite Subgraph Problem
NP-Completeness of co-NEVER-MINIMAL
Connections with the Syntactic Monoid Problem
Conclusions and Open Problems
References
Boolean Algebras of Regular Languages
Introduction
Preliminaries on Boolean Algebras
Preliminaries on Regular Languages
Boolean Algebra R
Boolean Algebra A
Conclusion
References
Fife's Theorem Revisited
Introduction
Notation
The Lexicographically Least Overlap-Free Word
Automatic Infinite Binary Overlap-Free Words
Remarks
References
Infinite Words Rich and Almost Rich in Generalized Palindromes
Introduction
Properties of Words with Finite -Defect
Proofs
Conclusion
References
Models of Pushdown Automata with Reset
Introduction
Preliminaries
Basic Notation
Basic Computation Models
PDA with Reset States
Resettable Pushdown Automata
Variants Equivalent to the 2PDA
Conclusion
References
Towards Dual Approaches for Learning Context-Free Grammars Based on Syntactic Concept Lattices
Introduction
Preliminaries
Syntactic Concept Lattices
Overview
Grammatical Representation of Syntactic Concept Lattices
Learning of Context-Free Grammars
Primal Approach
Dual Approach
Learning with the Maximal Bicliques
Concluding Remarks
References
On Highly Repetitive and Power Free Words
Introduction
Preliminary Definitions and Results
Highly Repetitive Binary Words
Highly Repetitive Ternary Words
Weaker Results on Ternary Words
Conclusion
References
A Sufficient Condition for Erasing Productions to Be Avoidable
Introduction
Basic Notions
Control Languages and Erasing Productions
Applications
References
Short Papers
Encoding Centered Polyominoes by Means of a Regular Language
References
Computational Aspects of Asynchronous Cellular Automata
References
Short 3-Collapsing Words over a 2-Letter Alphabet
References
A Cascade Decomposition of Weighted Finite Transition Systems
References
Morphic Characterizations in Terms of Insertion Systems with a Context of Length One
References
Inference of Residual Finite-State Tree Automata from Membership Queries and Finite Positive Data
References
On the Representability of Line Graphs
Introduction
Results
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken