Developments in Language Theory: 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings

Front Matter....Pages -
The Kind Hearted Dragon Prof. Sheng Yu, 1950-2012....Pages 1-6
P and dP Automata: Unconventional versus Classical Automata....Pages 7-22
Recovering Strings in Oracles: Quantum and Classic....Pages 23-23
Determinism vs. Nondeterminism for Two-Way Automata....Pages 24-39
Cellular Automata, the Collatz Conjecture and Powers of 3/2....Pages 40-49
Quotient Complexities of Atoms of Regular Languages....Pages 50-61
Decidability of Geometricity of Regular Languages....Pages 62-72
Inside the Class of REGEX Languages....Pages 73-84
Computing the Edit-Distance between a Regular Language and a Context-Free Language....Pages 85-96
Semigroups with a Context-Free Word Problem....Pages 97-108
Generalized Derivations with Synchronized Context-Free Grammars....Pages 109-120
Non-erasing Variants of the Chomsky–Schützenberger Theorem....Pages 121-129
Regular and Context-Free Pattern Languages over Small Alphabets....Pages 130-141
On Context-Free Languages of Scattered Words....Pages 142-153
Homomorphisms Preserving Deterministic Context-Free Languages....Pages 154-165
Unary Coded NP-Complete Languages in ASPACE (log log n)....Pages 166-177
Dense Completeness....Pages 178-189
From Equivalence to Almost-Equivalence, and Beyond—Minimizing Automata with Errors....Pages 190-201
Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata....Pages 202-213
States and Heads Do Count for Unary Multi-head Finite Automata....Pages 214-225
Visibly Pushdown Automata with Multiplicities: Finiteness and K -Boundedness....Pages 226-238
Unambiguous Constrained Automata....Pages 239-250
Two-Dimensional Sgraffito Automata....Pages 251-262
Two-Way Transducers with a Two-Way Output Tape....Pages 263-272
Learning Rational Functions....Pages 273-283
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata....Pages 284-295
Fine and Wilf’s Theorem for k -Abelian Periods....Pages 296-307
Pseudoperiodic Words....Pages 308-319
Acceptance Conditions for ω -Languages....Pages 320-331
Checking Determinism of Regular Expressions with Counting....Pages 332-343
Biautomata for k -Piecewise Testable Languages....Pages 344-355
On Centralized PC Grammar Systems with Context-Sensitive Components....Pages 356-367
Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars....Pages 368-379
The State Complexity of Star-Complement-Star....Pages 380-391
On State Complexity of Finite Word and Tree Languages....Pages 392-403
Squares in Binary Partial Words....Pages 404-415
The Avoidability of Cubes under Permutations....Pages 416-427
Hairpin Completion with Bounded Stem-Loop....Pages 428-439
Morphic Primitivity and Alphabet Reductions....Pages 440-451
On a Hierarchy of Languages with Catenation and Shuffle....Pages 452-458
Characterizing Languages by Normalization and Termination in String Rewriting....Pages 459-464
Geometry and Dynamics of the Besicovitch and Weyl Spaces....Pages 465-470
A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay....Pages 471-476
Back Matter....Pages -