Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings

Front Matter....Pages -
Measuring Information in Timed Languages....Pages 1-2
Automata-Based Symbolic Representations of Polyhedra....Pages 3-20
Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory....Pages 21-37
A Parameterized Complexity Tutorial....Pages 38-56
The Computer Science of DNA Nanotechnology....Pages 57-57
The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems....Pages 58-69
Unification Modulo Chaining....Pages 70-82
Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits....Pages 83-94
Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space....Pages 95-105
Defining Contexts in Context-Free Grammars....Pages 106-118
Longest Common Extensions via Fingerprinting....Pages 119-130
Fast and Cache-Oblivious Dynamic Programming with Local Dependencies....Pages 131-142
An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings....Pages 143-154
Strong Termination for Gap-Order Constraint Abstractions of Counter Systems....Pages 155-168
Covering Space in the Besicovitch Topology....Pages 169-178
Approximate Regular Expressions and Their Derivatives....Pages 179-191
Catalytic Petri Nets Are Turing Complete....Pages 192-203
Computational Complexity of Rule Distributions of Non-uniform Cellular Automata....Pages 204-215
Conservative Groupoids Recognize Only Regular Languages....Pages 216-227
Advice Complexity of Online Coloring for Paths....Pages 228-239
A Faster Grammar-Based Self-index....Pages 240-251
Learnability of Co-r.e. Classes....Pages 252-263
Two-Way Automata Making Choices Only at the Endmarkers....Pages 264-276
Polynomial-Time Algorithms for Learning Typed Pattern Languages....Pages 277-288
Forbidding Sets and Normal Forms for Language Forbidding-Enforcing Systems....Pages 289-300
Applying Tree Languages in Proof Theory....Pages 301-312
The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints....Pages 313-324
Characterizing the Rational Functions by Restarting Transducers....Pages 325-336
Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines....Pages 337-350
Feasible Automata for Two-Variable Logic with Successor on Data Words....Pages 351-362
Nash Equilibria in Concurrent Priced Games....Pages 363-376
Computing by Observing Insertion....Pages 377-388
On the Parameterized Complexity of Default Logic and Autoepistemic Logic....Pages 389-400
Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic....Pages 401-407
On Model Checking for Visibly Pushdown Automata....Pages 408-419
Automaton-Based Array Initialization Analysis....Pages 420-432
Dynamics of Circuits and Intersecting Circuits....Pages 433-444
Canonizable Partial Order Generators....Pages 445-457
Ogden’s Lemma for ET0L Languages....Pages 458-467
Patterns with Bounded Treewidth....Pages 468-479
P–NP Threshold for Synchronizing Road Coloring....Pages 480-489
 k -Automatic Sets of Rational Numbers....Pages 490-501
On Stable and Unstable Limit Sets of Finite Families of Cellular Automata....Pages 502-513
Automaton Ranks of Some Self-similar Groups....Pages 514-525
One-Way Reversible and Quantum Finite Automata with Advice....Pages 526-537
Integration of the Dual Approaches in the Distributional Learning of Context-Free Grammars....Pages 538-550
Back Matter....Pages -