Language and Automata Theory and Applications: Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008, Revised PapersCarlos Martin-Vide, Friedrich Otto, Henning Fernau 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 |
Contents
TreeWalking Automata | 1 |
Formal Language Tools for TemplateGuided DNA Recombination | 3 |
Subsequence Counting Matrix Representations and a Theorem of Eilenberg | 6 |
Synchronizing Automata and the vCerny Conjecture | 11 |
About Universal Hybrid Networks of Evolutionary Processors of Small Size | 28 |
On Bifix Systems and Generalizations | 40 |
Finite Automata Palindromes Powers and Patterns | 52 |
OneDimensional Quantum Cellular Automata over Finite Unbounded Configurations | 64 |
On Linear Logic Planning and Concurrency | 250 |
On the Relation between Multicomponent Tree Adjoining Grammars with Tree Tuples TTMCTAG and Range Concatenation Grammars RCG | 263 |
Antipattern Matching Modulo | 275 |
Counting Ordered Patterns in Words Generated by Morphisms | 287 |
Literal Varieties of Languages Induced by Homomorphisms onto Nilpotent Groups | 299 |
Characterization of StarConnected Languages Using Finite Automata | 311 |
MatchBounds with Dependency Pairs for Proving Termination of Rewrite Systems | 321 |
Further Results on InsertionDeletion Systems with OneSided Contexts | 333 |
The ThreeColor and TwoColor TantrixTM Rotation Puzzle Problems Are NPComplete Via Parsimonious Reductions | 76 |
Optional and Iterated Types for Pregroup Grammars | 88 |
Transformations and Preservation of Selfassembly Dynamics through Homotheties | 101 |
Deterministic InputReversal and InputRevolving Finite Automata | 113 |
Random Context in Regulated Rewriting Versus Cooperating Distributed Grammar Systems | 125 |
Extending the Overlap Graph for Gene Assembly in Ciliates | 137 |
Automatic Presentations for Cancellative Semigroups | 149 |
Induced Subshifts and Cellular Automata | 160 |
Hopcrofts Algorithm and Cyclic Automata | 172 |
Efficient Inclusion Checking for Deterministic Tree Automata and DTDs | 184 |
Consensual Definition of Languages by Regular Sets | 196 |
kPetri Net Controlled Grammars | 209 |
2Synchronizing Words | 221 |
Not So Many Runs in Strings | 232 |
A Hybrid Approach to Word Segmentation of Vietnamese Texts | 240 |
On RegularityPreservation by StringRewriting Systems | 345 |
Minimizing Deterministic Weighted Tree Automata | 357 |
Lower Bounds for Generalized Quantum Finite Automata | 373 |
How Many Figure Sets Are Codes? | 385 |
On Alternating PhraseStructure Grammars | 397 |
A TwoDimensional Taxonomy of Proper Languages of Lexicalized FRRAutomata | 409 |
Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NPHard | 421 |
Sorting and Element Distinctness on OneWay Turing Machines | 433 |
On Periodicity of Generalized TwoDimensional Words | 440 |
On the Analysis of Simple 2D Stochastic Cellular Automata | 452 |
Polycyclic and Bicyclic Valence Automata | 464 |
Length Codes Products of Languages and Primality | 476 |
An Efficient Algorithm for the Inclusion Problem of a Subclass of DPDAs | 487 |
| 499 | |
Other editions - View all
Common terms and phrases
accepted algebra algorithm alphabet anti-pattern applied automaton Berlin Heidelberg 2008 binary bound cell cellular automata centered function codes color Computer Science configuration consider construction contains context-free context-free grammar context-free languages Corollary corresponding defined Definition deletion denote derivation deterministic edge element equivalent example exists factor Fernau Eds finite automata finite set free monoids GQFA grammar systems Heidelberg Hence inclusion infinite input integer label Lemma length linear linear logic LNCS matching minimal monoid morphism multiset node NP-complete obtain occurrences p-group pattern Petri net polynomial production proof properties Proposition prove quantum random context rational regular languages relation reset word resp result rewriting systems rules semigroup sentential form sequence simulated Springer star-connected step subpuzzle subset symbols synchronizing Tantrix Theorem theory tile transitions tree automata Turing machines vertex