Mikołaj Bojańczyk (auth.), Carlos Martín-Vide, Friedrich Otto, Henning Fernau (eds.)3540882812, 9783540882817
This book constitutes the refereed proceedings of the Second International Conference on Language and Automata Theory and Applications, LATA 2008, held in Tarragona, Spain, in March 2008.
The 40 revised full papers presented were carefully reviewed and selected from 134 submissions. The papers deal with the various issues related to automata theory and formal languages
Table of contents :
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 –
Reviews
There are no reviews yet.