Developments in Language Theory: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings

Mikołaj Bojańczyk (auth.), Volker Diekert, Dirk Nowotka (eds.)3642027369, 9783642027369

This book constitutes the proceedings of the 13th International Conference, DLT 2009, held in Stuttgart, Germany from June 30 until July 3, 2009. The 35 papers presented together with 4 invited talks were carefully reviewed and selected from 70 submissions. The papers presented address topics on formal languages, automata theory, computability, complexity, logic, petri nets and related areas.

---

Table of contents :
Front Matter….Pages –
Factorization Forests….Pages 1-17
Weighted versus Probabilistic Logics….Pages 18-38
Post Correspondence Problem and Small Dimensional Matrices….Pages 39-46
Size Complexity of Two-Way Finite Automata….Pages 47-66
Matrix Mortality and the Černý-Pin Conjecture….Pages 67-80
A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata….Pages 81-90
Regular Languages Definable by Majority Quantifiers with Two Variables….Pages 91-102
The Inclusion Problem of Context-Free Languages: Some Tractable Cases….Pages 103-112
On the Complexity of Deciding Avoidability of Sets of Partial Words….Pages 113-124
Closures in Formal Languages and Kuratowski’s Theorem….Pages 125-144
Rich and Periodic-Like Words….Pages 145-155
Traces of Control-Flow Graphs….Pages 156-169
Left and Right Synchronous Relations….Pages 170-182
An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words….Pages 183-194
Asymptotic Cellular Complexity….Pages 195-206
Strongly Regular Grammars and Regular Approximation of Context-Free Languages….Pages 207-220
Powers of Regular Languages….Pages 221-227
Existence and Nonexistence of Descriptive Patterns….Pages 228-239
On Stateless Multihead Finite Automata and Multihead Pushdown Automata….Pages 240-251
On Negative Bases….Pages 252-263
Crucial Words for Abelian Powers….Pages 264-275
Tight Bounds on the Descriptional Complexity of Regular Expressions….Pages 276-287
Subshifts, Languages and Logic….Pages 288-299
Magic Numbers and Ternary Alphabet….Pages 300-311
The Pumping Lemma for Well-Nested Multiple Context-Free Languages….Pages 312-325
The Support of a Recognizable Series over a Zero-Sum Free, Commutative Semiring Is Recognizable….Pages 326-333
A Game-Theoretic Characterization of Boolean Grammars….Pages 334-347
Word Equations with One Unknown….Pages 348-359
On Equations over Sets of Numbers and Their Limitations….Pages 360-371
Some Remarks on Superposition Based on Watson-Crick-Like Complementarity….Pages 372-383
A Weighted μ -Calculus on Words….Pages 384-395
Branching-Time Temporal Logics with Minimal Model Quantifiers….Pages 396-409
Simulations by Time-Bounded Counter Machines….Pages 410-418
Weighted Timed MSO Logics….Pages 419-430
Balanced Words Having Simple Burrows-Wheeler Transform….Pages 431-442
On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations….Pages 443-453
Definability in the Infix Order on Words….Pages 454-465
Two-Sided Bounds for the Growth Rates of Power-Free Languages….Pages 466-477
On the Decidability of the Equivalence for a Certain Class of Transducers….Pages 478-489
Erasing in Petri Net Languages and Matrix Grammars….Pages 490-501
Back Matter….Pages –