Language and automata theory and applications third international conference, LATA 2009, Tarragona, Spain, April 2-8, 2009, proceedings

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 -