Developments in language theory : 15th international conference, DLT 2011, Milano, Italy, July 19-22, 2011 ; proceedings

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. Front Matter....Pages - Hunting Redundancies in Strings....Pages 1-14 Some Remarks on Automata Minimality....Pages 15-27 Growth Properties of Power-Free Languages....Pages 28-43 A Functional Program for Regular Expressions Matching....Pages 44-45 State Complexity Research and Approximation....Pages 46-57 Counting the Orderings for Multisets in Consecutive Ones Property and PQ-Trees....Pages 58-69 Avoiding Abelian Powers in Partial Words....Pages 70-81 Regular Splicing Languages Must Have a Constant....Pages 82-92 The Average Transition Complexity of Glushkov and Partial Derivative Automata....Pages 93-104 Theory of Átomata....Pages 105-116 Syntactic Complexity of Ideal and Closed Languages....Pages 117-128 Generalized One-Unambiguity....Pages 129-140 Simulations over Two-Dimensional On-Line Tessellation Automata....Pages 141-152 Δ-Clearing Restarting Automata and $\makebox{\sf CFL} $ ....Pages 153-164 Enumeration and Decidable Properties of Automatic Sequences....Pages 165-179 Languages vs. ω -Languages in Regular Infinite Games....Pages 180-191 Solving Word Problems in Group Extensions over Infinite Words....Pages 192-203 Abelian Primitive Words....Pages 204-215 Scattered Context-Free Linear Orderings....Pages 216-227 On Prefix Normal Words....Pages 228-238 On Non-complete Sets and Restivo’s Conjecture....Pages 239-250 Self-organization in Cellular Automata: A Particle-Based Approach....Pages 251-263 Chop Operations and Expressions: Descriptional Complexity Considerations....Pages 264-275 Nodes Connected by Path Languages....Pages 276-287 Characterizing the Regular Languages by Nonforgetting Restarting Automata....Pages 288-299 On Two-Way Transducers....Pages 300-311 There Does Not Exist a Minimal Full Trio with Respect to Bounded Context-Free Languages....Pages 312-323 Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups....Pages 324-336 Deciding Networks of Evolutionary Processors....Pages 337-349 From Linear Partitions to Parallelogram Polyominoes....Pages 350-361 On Brzozowski’s Conjecture for the Free Burnside Semigroup Satisfying x 2 = x 3 ....Pages 362-373 Never Minimal Automata and the Rainbow Bipartite Subgraph Problem....Pages 374-385 Boolean Algebras of Regular Languages....Pages 386-396 Fife’s Theorem Revisited....Pages 397-405 Infinite Words Rich and Almost Rich in Generalized Palindromes....Pages 406-416 Models of Pushdown Automata with Reset....Pages 417-428 Towards Dual Approaches for Learning Context-Free Grammars Based on Syntactic Concept Lattices....Pages 429-440 On Highly Repetitive and Power Free Words....Pages 441-451 A Sufficient Condition for Erasing Productions to Be Avoidable....Pages 452-463 Encoding Centered Polyominoes by Means of a Regular Language....Pages 464-465 Computational Aspects of Asynchronous Cellular Automata....Pages 466-468 Short 3-Collapsing Words over a 2-Letter Alphabet....Pages 469-471 A Cascade Decomposition of Weighted Finite Transition Systems....Pages 472-473 Morphic Characterizations in Terms of Insertion Systems with a Context of Length One....Pages 474-475 Inference of Residual Finite-State Tree Automata from Membership Queries and Finite Positive Data....Pages 476-477 On the Representability of Line Graphs....Pages 478-479 Back Matter....Pages -