Development in Language Theory
15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings
Published on 12. July 2011
XIV, 482 pages
978-3-642-22321-1 (ISBN)
Description
This book constitutes the refereed proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011, held in Milano, Italy, in July 2011. The 34 regular papers presented were carefully reviewed and selected from numerous submissions. The volume also contains the papers or abstracts of 5 invited speakers, as well as a 2-page abstract for each of the 7 poster papers. The topics covered include grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; codes; symbolic dynamics; algorithmic, combinatorial and algebraic properties of words and languages; decidability questions; applications of language theory, including: natural computing, image manipulation and compression, text algorithms, cryptography, concurrency, complexity theory and logic; cellular automata and multidimensional patterns; language theory aspects of quantum computing and bio-computing.
More details
Other editions
Additional editions
Giancarlo Mauri | Alberto Leporati
Development in Language Theory
15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings
Book
07/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- 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
