Developments in Language Theory

Invited Talks.- Iteration Semirings.- Various Aspects of Finite Quantum Automata.- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes.- Selected Ideas Used for Decidability and Undecidability of Bisimilarity.- The Frobenius Problem and Its Generalizations.- Well Quasi-orders in Formal Language Theory.- Contributed Papers.- On the Non-deterministic Communication Complexity of Regular Languages.- General Algorithms for Testing the Ambiguity of Finite Automata.- Emptiness of Multi-pushdown Automata Is 2ETIME-Complete.- The Average State Complexity of the Star of a Finite Set of Words Is Linear.- On the Computational Capacity of Parallel Communicating Finite Automata.- On a Generalization of Standard Episturmian Morphisms.- Universal Recursively Enumerable Sets of Strings.- Algorithmically Independent Sequences.- Relationally Periodic Sequences and Subword Complexity.- Bounds on Powers in Strings.- When Is Reachability Intrinsically Decidable?.- Some New Modes of Competence-Based Derivations in CD Grammar Systems.- The Synchronization Problem for Strongly Transitive Automata.- On the Decidability of the Equivalence for k-Valued Transducers.- Decidable Properties of 2D Cellular Automata.- Fixed Point and Aperiodic Tilings.- Extended Multi Bottom-Up Tree Transducers.- Derivation Tree Analysis for Accelerated Fixed-Point Computation.- Tree Automata with Global Constraints.- Bad News on Decision Problems for Patterns.- Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time.- More Concise Representation of Regular Languages by Automata and Regular Expressions.- A Taxonomy of Deterministic Forgetting Automata.- Provably Shorter Regular Expressions from Deterministic Finite Automata.- Large Simple Binary Equality Words.- On the Relation between Periodicity and Unbordered Factors of Finite Words.- Duplication in DNA Sequences.- On the State Complexity of Complements, Stars, and Reversals of Regular Languages.- On the State Complexity of Operations on Two-Way Finite Automata.- On the Size Complexity of Rotating and Sweeping Automata.- An Analysis and a Reproof of Hmelevskii’s Theorem.- Hierarchies of Piecewise Testable Languages.- Construction of Tree Automata from Regular Expressions.- Balance Properties and Distribution of Squares in Circular Words.- MSO Logic for Unambiguous Shared-Memory Systems.- Complexity of Topological Properties of Regular ?-Languages.