Developments in Language Theory 1st Edition by Arseny Shur, Mikhail Volkov ISBN 3319096982 97

Infinite Transitive Automatic Graphs

1. Introduction
2. Contributions of the Paper
3. Examples of Infinite Transitive Automatic Graphs
4. Baumslag–Solitar Groups
5. Wreath Products
   • Wreath Products of Finitely Generated Groups and Z
   • Generalization
   • Is the Wreath Product Z2 Z2 Cayley Automatic?
6. References

Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals

1. Introduction
2. Preliminaries
3. Left Ideals
   • Basic Properties
   • Upper Bound
4. Two-Sided Ideals
5. References

Brzozowski’s Algorithm for Deterministic Automata

1. Introduction
2. Definitions
3. Result for a Large Number of Final States
4. Main Result
5. Proof of Theorem for Automata with One Final State
   • Finding Specific Substrings
   • Completing the Proof
6. General Case
7. References

State Complexity of Deletion

1. Introduction
2. Preliminaries
3. Upper Bound for Deletion
4. Lower Bound Constructions
   • Complete DFAs
   • Incomplete DFAs
5. Conclusion and Further Work
6. References

Semisimple Synchronizing Automata and the Wedderburn-Artin Theory

1. Introduction
2. The Radical of a Synchronizing Automaton
3. Semisimple Synchronizing Automata
4. Factoring the Problem via the Wedderburn-Artin Theorem
5. Černý’s Conjecture for Strongly Semisimple Synchronizing Automata
6. Open Problems
7. References

Synchronization in Automata

1. Testing for Synchronization
2. Approximation of Reset Thresholds
3. References

Graph Spectral Properties of Deterministic Finite Automata

1. Introduction
2. Nerode Partition and Equitable Partition
   • Automata and Languages
   • Graphs and Adjacency Matrices
3. Minimality Properties of Minimal Automata
4. Rank-one Languages and Expanded Canonical Automata
5. References

Pushdown Automata and Related Models

1. Input-Driven Pushdown Automata with Limited Nondeterminism
2. Decision Problems
3. References

Visibly Pushdown Transducers with Well-Nested Outputs

1. Introduction
2. Classes of VPT Producing Well-Nested Outputs
3. Closure under Composition
4. References

Algebraic and Complexity Problems in Automata Systems

1. Measuring Communication in Automata Systems
   • Weakly Parallel Systems
   • Massively Parallel Systems
2. From Algebra to Logic: A Hierarchy Story
3. Closure Properties of Pattern Languages
   • Terminal-Free Patterns
4. Minimal and Hyper-Minimal Biautomata
5. Deterministic Set Automata
6. References