Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings

Front Matter....Pages -
Green’s Relations and Their Use in Automata Theory....Pages 1-21
Automatic Structures and Groups....Pages 22-40
Vector Addition System Reachability Problem: A Short Self-contained Proof....Pages 41-64
Abstract Numeration Systems....Pages 65-79
Rule Formats for Distributivity....Pages 80-91
Mutation Systems....Pages 92-104
Classification of String Languages via Tiling Recognizable Picture Languages....Pages 105-116
A Simple and Efficient Universal Reversible Turing Machine....Pages 117-128
The Parameterized Complexity of Chosen Problems for Finite Automata on Trees....Pages 129-141
Recognizing Shuffled Languages....Pages 142-154
Unary Pattern Avoidance in Partial Words Dense with Holes....Pages 155-166
Characterizing Compressibility of Disjoint Subgraphs with NLC Grammars....Pages 167-178
Partial Derivatives of an Extended Regular Expression....Pages 179-191
Automatic Learning of Subclasses of Pattern Languages....Pages 192-203
Finite Orbits of Language Operations....Pages 204-215
Finitary Languages....Pages 216-226
The Complexity of Request-Response Games....Pages 227-237
Improved Alignment Based Algorithm for Multilingual Text Compression....Pages 238-249
Singular Artin Monoids of Finite Coxeter Type Are Automatic....Pages 250-261
Networks of Evolutionary Processors with Subregular Filters....Pages 262-273
Decision Problems for Interval Markov Chains....Pages 274-285
Classifying Regular Languages via Cascade Products of Automata....Pages 286-297
The Block Structure of Successor Morphisms....Pages 298-309
Models for Quantitative Distributed Systems and Multi-Valued Logics....Pages 310-322
A Local Greibach Normal Form for Hyperedge Replacement Grammars....Pages 323-335
Unique Small Subgraphs Are Not Easier to Find....Pages 336-341
Simplifying DPDA Using Supplementary Information....Pages 342-353
Normalization of Sequential Top-Down Tree-to-Word Transducers....Pages 354-365
Planarity of Knots, Register Automata and LogSpace Computability....Pages 366-377
Tarski’s Principle, Categorial Grammars and Learnability....Pages 378-389
Globally Deterministic CD-Systems of Stateless R(1)-Automata....Pages 390-401
Bit-coded Regular Expression Parsing....Pages 402-413
Descriptional Complexity of Unambiguous Nested Word Automata....Pages 414-426
Avalanche Structure in the Kadanoff Sand Pile Model....Pages 427-439
Well-Quasi-Ordering Hereditarily Finite Sets....Pages 440-451
On the Interval-Bound Problem for Weighted Timed Automata....Pages 452-464
Finding Shuffle Words That Represent Optimal Scheduling of Shared Memory Access....Pages 465-476
Syntactic Complexity of Ultimately Periodic Sets of Integers....Pages 477-488
Undecidability of the State Complexity of Composed Regular Operations....Pages 489-498
Restarting Automata with Auxiliary Symbols and Small Lookahead....Pages 499-510
Back Matter....Pages -