Language and Automata Theory and Applications: Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers

Front Matter....Pages -
Tree-Walking Automata....Pages 1-2
Formal Language Tools for Template-Guided DNA Recombination....Pages 3-5
Subsequence Counting, Matrix Representations and a Theorem of Eilenberg....Pages 6-10
Synchronizing Automata and the Černý Conjecture....Pages 11-27
About Universal Hybrid Networks of Evolutionary Processors of Small Size....Pages 28-39
On Bifix Systems and Generalizations....Pages 40-51
Finite Automata, Palindromes, Powers, and Patterns....Pages 52-63
One-Dimensional Quantum Cellular Automata over Finite, Unbounded Configurations....Pages 64-75
The Three-Color and Two-Color Tantrix TM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions....Pages 76-87
Optional and Iterated Types for Pregroup Grammars....Pages 88-100
Transformations and Preservation of Self-assembly Dynamics through Homotheties....Pages 101-112
Deterministic Input-Reversal and Input-Revolving Finite Automata....Pages 113-124
Random Context in Regulated Rewriting Versus Cooperating Distributed Grammar Systems....Pages 125-136
Extending the Overlap Graph for Gene Assembly in Ciliates....Pages 137-148
Automatic Presentations for Cancellative Semigroups....Pages 149-159
Induced Subshifts and Cellular Automata....Pages 160-171
Hopcroft’s Algorithm and Cyclic Automata....Pages 172-183
Efficient Inclusion Checking for Deterministic Tree Automata and DTDs....Pages 184-195
Consensual Definition of Languages by Regular Sets....Pages 196-208
 k -Petri Net Controlled Grammars....Pages 209-220
2-Synchronizing Words....Pages 221-231
Not So Many Runs in Strings....Pages 232-239
A Hybrid Approach to Word Segmentation of Vietnamese Texts....Pages 240-249
On Linear Logic Planning and Concurrency....Pages 250-262
On the Relation between Multicomponent Tree Adjoining Grammars with Tree Tuples (TT-MCTAG) and Range Concatenation Grammars (RCG)....Pages 263-274
Anti-pattern Matching Modulo....Pages 275-286
Counting Ordered Patterns in Words Generated by Morphisms....Pages 287-298
Literal Varieties of Languages Induced by Homomorphisms onto Nilpotent Groups....Pages 299-310
Characterization of Star-Connected Languages Using Finite Automata....Pages 311-320
Match-Bounds with Dependency Pairs for Proving Termination of Rewrite Systems....Pages 321-332
Further Results on Insertion-Deletion Systems with One-Sided Contexts....Pages 333-344
On Regularity-Preservation by String-Rewriting Systems....Pages 345-356
Minimizing Deterministic Weighted Tree Automata....Pages 357-372
Lower Bounds for Generalized Quantum Finite Automata....Pages 373-384
How Many Figure Sets Are Codes?....Pages 385-396
On Alternating Phrase-Structure Grammars....Pages 397-408
A Two-Dimensional Taxonomy of Proper Languages of Lexicalized FRR-Automata....Pages 409-420
Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard....Pages 421-432
Sorting and Element Distinctness on One-Way Turing Machines....Pages 433-439
On Periodicity of Generalized Two-Dimensional Words....Pages 440-451
On the Analysis of “Simple” 2D Stochastic Cellular Automata....Pages 452-463
Polycyclic and Bicyclic Valence Automata....Pages 464-475
Length Codes, Products of Languages and Primality....Pages 476-486
An Efficient Algorithm for the Inclusion Problem of a Subclass of DPDAs....Pages 487-498
Back Matter....Pages -