Language And Automata Theory And Applications: Third International Conference, Lata 2009, Tarragona, Spain, April 2-8, 2009. Proceedings (lecture Notes In Computer Science)

This book constitutes the refereed proceedings of the Third International Conference on Language and Automata Theory and Applications, LATA 2009, held in Tarragona, Spain, in April 2009. The 58 revised full papers presented together with 3 invited lectures and two tutorials were carefully reviewed and selected from 121 submissions. The papers address all the various issues related to automata theory and formal languages. Front Matter....Pages - Recent Developments in Algorithmic Teaching....Pages 1-18 Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications....Pages 19-22 Descriptional and Computational Complexity of Finite Automata....Pages 23-42 Hypothesis Spaces for Learning....Pages 43-58 State Complexity of Nested Word Automata....Pages 59-70 A Language-Based Comparison of Extensions of Petri Nets with and without Whole-Place Operations....Pages 71-82 Minimal Union-Free Decompositions of Regular Languages....Pages 83-92 Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory....Pages 93-104 Matching Trace Patterns with Regular Policies....Pages 105-116 Absolute Convergence of Rational Series Is Semi-decidable....Pages 117-128 Non-solvable Groups Are Not in FO+MOD+MÂJ 2 [REG]....Pages 129-140 Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights....Pages 141-151 Refinement and Consistency of Timed Modal Specifications....Pages 152-163 Nondeterministic Instance Complexity and Proof Systems with Advice....Pages 164-175 How Many Holes Can an Unbordered Partial Word Contain?....Pages 176-187 An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms....Pages 188-199 Partial Projection of Sets Represented by Finite Automata, with Application to State-Space Visualization....Pages 200-211 Larger Lower Bounds on the OBDD Complexity of Integer Multiplication....Pages 212-223 Picture Languages Generated by Assembling Tiles....Pages 224-235 Undecidability of Operation Problems for T0L Languages and Subclasses....Pages 236-246 Decision Problems for Convex Languages....Pages 247-258 On a Family of Morphic Images of Arnoux-Rauzy Words....Pages 259-266 Monadic Datalog Tree Transducers....Pages 267-278 On Extended Regular Expressions....Pages 279-289 Multi-tilde Operators and Their Glushkov Automata....Pages 290-301 Non-uniform Cellular Automata....Pages 302-313 A Cryptosystem Based on the Composition of Reversible Cellular Automata....Pages 314-325 Grammars Controlled by Special Petri Nets....Pages 326-337 Nested Counters in Bit-Parallel String Matching....Pages 338-349 Bounded Delay and Concurrency for Earliest Query Answering....Pages 350-361 Learning by Erasing in Dynamic Epistemic Logic....Pages 362-373 The Fault Tolerance of NP-Hard Problems....Pages 374-385 Termination of Priority Rewriting....Pages 386-397 State Complexity of Combined Operations for Prefix-Free Regular Languages....Pages 398-409 Towards a Taxonomy for ECFG and RRPG Parsing....Pages 410-421 Counting Parameterized Border Arrays for a Binary Alphabet....Pages 422-433 Bounded Hairpin Completion....Pages 434-445 Rigid Tree Automata....Pages 446-457 Converting Self-verifying Automata into Deterministic Automata....Pages 458-468 Two Equivalent Regularizations for Tree Adjoining Grammars....Pages 469-480 Self-overlapping Occurrences and Knuth-Morris-Pratt Algorithm for Weighted Matching....Pages 481-492 Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata....Pages 493-504 Automata on Gauss Words....Pages 505-517 Analysing Complexity in Classes of Unary Automatic Structures....Pages 518-529 An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words....Pages 530-541 Segmentation Charts for Czech – Relations among Segments in Complex Sentences....Pages 542-553 A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions....Pages 554-565 Efficiency of the Symmetry Bias in Grammar Acquisition....Pages 566-577 A Series of Run-Rich Strings....Pages 578-587 On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes....Pages 588-600 The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates....Pages 601-613 Prediction of Creole Emergence in Spatial Language Dynamics....Pages 614-625 On the Average Size of Glushkov’s Automata....Pages 626-637 Tiling the Plane with a Fixed Number of Polyominoes....Pages 638-647 New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality....Pages 648-659 On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata....Pages 660-671 Finitely Generated Synchronizing Automata....Pages 672-683 Genetic Algorithm for Synchronization....Pages 684-695 Constructing Infinite Words of Intermediate Arithmetical Complexity....Pages 696-701 From Gene Trees to Species Trees through a Supertree Approach....Pages 702-714 A Kleene Theorem for Forest Languages....Pages 715-727 Determinization and Expressiveness of Integer Reset Timed Automata with Silent Transitions....Pages 728-739 One-Clock Deterministic Timed Automata Are Efficiently Identifiable in the Limit....Pages 740-751 Back Matter....Pages - This book constitutes the refereed proceedings of the 7th International Conference on Language and Automata Theory and Applications, LATA 2013, held in Bilbao, Spain in April 2013. trees, tree languages and tree automata;