Developments in Language Theory

Restricted Towers of Hanoi and Morphisms.- Collapsing Words: A Progress Report.- Locally Consistent Parsing and Applications to Approximate String Comparisons.- Central Sturmian Words: Recent Developments.- Reversible Cellular Automata.- Inexpressibility Results for Regular Languages in Nonregular Settings.- Complexity of Quantum Uniform and Nonuniform Automata.- Membership and Finiteness Problems for Rational Sets of Regular Languages.- Tissue P Systems with Antiport Rules and Small Numbers of Symbols and Cells.- The Mortality Threshold for Partially Monotonic Automata.- Sturmian Words: Dynamical Systems and Derivated Words.- Schützenberger and Eilenberg Theorems for Words on Linear Orderings.- On the Membership of Invertible Diagonal Matrices.- A Kleene Theorem for Languages of Words Indexed by Linear Orderings.- Revolving-Input Finite Automata.- Some New Results on Palindromic Factors of Billiard Words.- A Note on a Result of Daurat and Nivat.- Palindromes in Sturmian Words.- Voronoi Cells of Beta-Integers.- Languages with Mismatches and an Application to Approximate Indexing.- Bidimensional Sturmian Sequences and Substitutions.- Unambiguous Morphic Images of Strings.- Complementing Two-Way Finite Automata.- On Timed Automata with Discrete Time – Structural and Language Theoretical Characterization.- Monotone Deterministic RL-Automata Don’t Need Auxiliary Symbols.- On Hairpin-Free Words and Languages.- Adding Monotonic Counters to Automata and Transition Graphs.- Polynomial Generators of Recursively Enumerable Languages.- On Language Inequalities XK???LX.- The Power of Tree Series Transducers of Type I and II.- The Inclusion Problem for Unambiguous Rational Trace Languages.- LR Parsing for Boolean Grammars.- On Some Properties of the Language of2-Collapsing Words.- Semi-rational Sets of DAGs.- On the Frequency of Letters in Pure Binary Morphic Sequences.

Includes supplementary material: sn.pub/extras