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

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 -