Language and Automata Theory and Applications
5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011
Published on 27. May 2011
XIII, 512 pages
978-3-642-21254-3 (ISBN)
Description
This book constitutes the refereed proceedings of the 5th International Conference on Language and Automata Theory and Applications, LATA 2011, held in Tarragona, Spain in May 2011. The 36 revised full papers presented together with four invited articles were carefully selected from 91 submissions. Among the topics covered are algebraic language theory, automata and logic, systems analysis, systems verifications, computational complexity, decidability, unification, graph transformations, language-based cryptography, and applications in data mining, computational learning, and pattern recognition.
More details
Other editions
Additional editions
Adrian-Horia Dediu | Carlos Martín-Vide | Shunsuke Inenaga
Language and Automata Theory and Applications
5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011
Book
05/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Invited Talks
- Green's Relations and Their Use in Automata Theory
- Basics on Monoids
- Schützenberger's Characterization of Star-Free Languages
- The Theorem of Factorization Forests of Simon
- On ?-Semigroups and Monadic Logic
- The Characterization of Decidable Theories by Semenov
- Deterministic Automata over ?-Words: McNaughton
- References
- Automatic Structures and Groups
- Introduction
- Basics
- Decidability and Definability Theorem
- Domain Dependency
- Automaticity in Groups
- Thurston Automaticity vs. Cayley Automaticity
- The Isomorphism Problem
- References
- Vector Addition System Reachability Problem: A Short Self-contained Proof
- Introduction
- Notations
- Definable Conic Sets
- Presburger Sets and almost Semilinear Sets
- Linearizations
- Presburger Invariants
- Vector Addition Systems
- Asymptotically Definable Production Relations
- Almost Semilinear Reachability Relations
- Conclusion
- References
- Abstract Numeration Systems
- Introduction
- Integer Bases
- Basic Definitions and Results
- Cobham's Theorem and Periodicity
- Alternative Characterizations
- k-Recognizable Sets and Number Theory
- Linear Numeration Systems
- Basic Definitions and Results
- Bertrand Systems
- Pisot Systems
- Further Discussion
- Abstract Numeration Systems
- Basic Definitions and Results
- Alternative Characterizations
- Further Discussion
- References
- Regular Papers
- Rule Formats for Distributivity
- Introduction
- Preliminaries
- Transition System Specifications and Bisimilarity
- The Left-Distributivity Rule Formats
- The Firability Condition
- The Matching-Conclusion Condition
- Examples of Application of the Rule Format
- Analyzing Targets of Conclusions of Deduction Rules
- References
- Mutation Systems
- Introduction
- Preliminaries
- MutationSystems
- Point Mutations
- Conservation of Strictly k-Testable Patterns
- Simulating FSM Computation
- From FSMs to Mutation Systems
- Correctness of the FSM Simulation
- Simulating Cellular Automata
- From Cellular Automata to Mutation Systems
- Defining the Fitness Function
- Correctness of the Cellular Automaton Simulation
- Discussion
- References
- Classification of String Languages via Tiling Recognizable Picture Languages
- Introduction
- Preliminaries
- Tiling Recognizable Picture Languages
- Family REC and Context-Sensitive String Languages
- Recognition of String Languages via Picture Languages
- Further Examples and Remarks
- Classification of String Languages by Picture Languages
- Conclusions and Future Works
- References
- A Simple and Efficient Universal Reversible Turing Machine
- Introduction
- Reversible Turing Machines
- Universality for RTMs
- A First-Principles URTM
- Related Work
- Conclusion
- References
- The Parameterized Complexity of Chosen Problems for Finite Automata on Trees
- Introduction
- The Parameterized Complexity Theory
- Finite Automata
- Preliminaries
- Classes of Automata
- Parameterized Decision Problems for Finite Automata on Trees
- Known Results
- Results
- Classical Tree Automata (TA)
- Rigid Tree Automata (RTA) and Tree Automata with Equalities and Disequalities (TAGED)
- Automata on DAG Representations of Finite Trees (t-DAG Automata)
- Conclusion
- References
- Recognizing Shuffled Languages
- Introduction
- Preliminaries
- Concurrent Finite-State Automata
- Membership Problems
- Conclusions and Future Work
- References
- Unary Pattern Avoidance in Partial Words Dense with Holes
- Introduction
- Preliminaries
- Hole Sparsity
- Non-trivial Minimum Hole Sparsity for Unary Patterns
- Minimum Hole Sparsity for Unary Patterns
- Conclusion
- References
- Characterizing Compressibility of Disjoint Subgraphs with NLC Grammars
- Introduction
- Related Work
- Notation and Terminology
- NLC Graph Grammars
- Compatibility and Confluency
- Touching Subgraphs
- Symmetric Connections
- Discussion
- References
- Partial Derivatives of an Extended Regular Expression
- Introduction
- Preliminaries
- Partial Derivatives of an Extended Expression
- A Natural Extension
- Set of Sets Extension
- The Derivated Term Automaton
- The Partial Derivative Automaton
- Conclusion
- References
- Automatic Learning of Subclasses of Pattern Languages
- Introduction
- The Model
- Classes of Pattern Languages
- Character Variables
- References
- Finite Orbits of Language Operations
- Introduction
- Operations with Infinite Orbit
- Kuratowski Identities
- Additional Identities
- Results
- Prefix and Complement
- Prefix, Kleene Star, Complement
- Factor, Kleene Star, Complement
- Kleene Star, Prefix, Suffix, Factor
- Summary of Results
- FurtherWork
- References
- Finitary Languages
- Introduction
- Definitions
- Topological Complexity of Languages
- Finitary Languages
- Automata, ?-Regular and Finitary Languages
- Topological Complexity
- Expressive Power of Finitary Automata
- Comparison with Classical Automata
- Deterministic Finitary Automata
- Non-deterministic Finitary Automata
- Closure Properties
- Regular Expression Characterization
- Decision Problems
- References
- The Complexity of Request-Response Games
- Introduction
- Definitions
- Complexity of Request-Response Games
- Request-Response Games Are EXPTIME-Complete
- Strategy Complexity
- Restrictions
- DAG Arenas
- One-Player Arenas
- References
- Improved Alignment Based Algorithm for Multilingual Text Compression
- Introduction
- Multilingual Compression Algorithm
- Results and Analysis
- Conclusion
- References
- Singular Artin Monoids of Finite Coxeter Type Are Automatic
- Introduction
- Automaticity via Rational Relations
- TheResults
- The Positive Singular Artin Monoid MG
- The Language of Normal Forms
- Automaticity of MG
- Automaticity of the Singular Artin Monoid M?
- References
- Networks of Evolutionary Processors with Subregular Filters
- Introduction
- Definitions
- Some General Results
- Computationally Complete Cases
- Computationally Non-complete Cases
- Conclusion
- References
- Decision Problems for Interval Markov Chains
- Introduction
- Background
- Refinement Relations
- Determinism
- Common Implementation and Consistency
- Related Work and Conclusion
- References
- Classifying Regular Languages via Cascade Products of Automata
- Introduction
- Preliminaries
- Piecewise Testable Languages
- Commutative Languages
- The Scope of Cascade Products
- Cascade Products and Dot-Depth
- Conclusion
- References
- The Block Structure of Successor Morphisms
- Introduction
- Basic Concepts and Definitions
- One Letter Bound for Successor Morphisms
- Block Structure of Successor Morphisms 3074
- Reduction Sequence of Successor Morphisms
- References
- Models for Quantitative Distributed Systems and Multi-Valued Logics
- Introduction
- Background: Traces and Asynchronous Cellular Automata
- Traces and Finite Automata
- Asynchronous Cellular Automata
- MSO Logic on Traces
- Weighted Asynchronous Cellular Automata
- Valuation Monoids and Weighted Finite Automata
- Weighted Asynchronous Cellular Automata
- The I-diamond Property and Its Relationship to wACAs
- Weighted MSO Logics
- Product Valuation Monoids
- Weighted MSO Logics for Traces
- The Relationship between wMSO Logics for Traces and Words
- Discussion
- References
- A Local Greibach Normal Form for Hyperedge Replacement Grammars
- Introduction
- Preliminaries
- Heaps and Hypergraphs
- Data Structures and Hyperedge Replacement Grammars
- Execution of Program Statements
- Heap Abstraction Grammars
- Local Greibach Normal Form
- Related Work
- Conclusion
- References
- Unique Small Subgraphs Are Not Easier to Find
- Introduction
- A Reduction to Instances with at Most One Occurrence
- Conclusions
- References
- Simplifying DPDA Using Supplementary Information
- Introduction
- Deterministic Pushdown Automata
- Complexity of Deterministic Context-Free Languages
- Measuring Complexity of Automata
- State Complexity
- Usefulness of Supplementary Information
- Decomposable Languages
- Non-decomposable Languages
- Conclusion
- References
- Normalization of Sequential Top-Down Tree-to-Word Transducers
- Introduction
- Sequential Top-Down Tree-to-Word Transducers
- Output Normalization
- Reducing Languages
- Pushing Words through Languages
- Pushing Words Backwards
- Output Normalization Algorithm
- Exponential Lower Bound
- Minimization
- Conclusions and Future Work
- References
- Planarity of Knots, Register Automata and LogSpace Computability
- Introduction
- Preliminaries
- Automata over an Infinite Alphabet
- Knots
- Planarity of Knot Diagrams Represented by Gauss Words
- Main Results
- Cairns-Elton Algorithm
- Implementation of Cairns-Elton Algorithm
- RA to LOGSPACE
- UNSIGNED PLANARITY in L
- LOGSPACE to DRA
- Conclusion
- References
- Tarski's Principle, Categorial Grammars and .Learnability
- Introduction
- Preliminaries
- Functor-Argument Structures
- Substitutions
- Functorial Languages
- Functorial Contexts
- Types and Grammars
- Unification
- Learnability
- References
- Globally Deterministic CD-Systems of Stateless R(1)-Automata
- Introduction
- CD-Systems of Stateless Deterministic R(1)-Automata
- Globally Deterministic CD-R(1)-Systems
- Decision Problems
- Concluding Remarks
- References
- Bit-coded Regular Expression Parsing
- Introduction
- Regular Expressions as Types
- Bit-coded Parse Trees
- Parsing Algorithms
- Dubé/Feeley-Style Parsing
- Frisch/Cardelli-Style Parsing
- Empirical Evaluation
- Backtracking Worst Case: (an: (a+1)nan)
- DFA Worst Case (am+1: (a+b)a (a+b)n)
- Practical Examples
- Conclusion
- References
- Descriptional Complexity of Unambiguous Nested Word Automata
- Introduction
- Preliminaries
- Lower Bounds for the Size of Nested Word Automata
- From Unambiguous to Deterministic
- From Nondeterministic to Unambiguous
- Complementing Nondeterministic Automata
- Homomorphic Images of Deterministic Automata
- Conclusion
- References
- Avalanche Structure in the Kadanoff Sand Pile Model
- Introduction
- Kadanoff Sand Pile Model
- Strategies and Avalanches
- The Context
- Avalanche Process in the General Case
- Short Transitional Phase When $D$ = 3
- Perspectives
- References
- Well-Quasi-Ordering Hereditarily Finite Sets
- Introduction
- Basics and Notation
- Sets and Digraphs
- Well-Quasi-Orders and Digraph Immersion
- Slim Sets and Discrimination
- Encoding
- Main Result
- Conclusion
- References
- On the Interval-Bound Problem for Weighted Timed Automata
- Introduction
- Preliminaries
- Undecidability Result
- Decidability Result
- The Addition Widget
- Other Widgets
- Arrangement of the Widgets
- Open Problems
- References
- Finding Shuffle Words That Represent Optimal Scheduling of Shared Memory Access
- Introduction
- Basic Definitions
- The Problem of Computing Shuffle Words with Minimum Scope Coincidence Degree
- Further Properties of the Scope Coincidence Degree
- Solving the Problem SWminSCDS
- References
- Syntactic Complexity of Ultimately Periodic Sets of Integers
- Introduction
- Definitions
- Main Results
- Application to a Decision Procedure
- Further Work
- References
- Undecidability of the State Complexity of Composed Regular Operations
- Introduction
- Diophantine Preliminaries
- State Complexity. Auxiliary Results from Automata Theory
- Undecidability
- Further Considerations and Open Problems
- The Effect of the Undecidability Reduction on the Associated Operations
- Borderline between Decidability and Undecidability
- Regularity-Preserving Operations Associated with Classes of Functions
- References
- Restarting Automata with Auxiliary Symbols and Small Lookahead
- Introduction
- Preliminaries
- Four Useful Properties
- MainResults
- Concluding Remarks
- References
- Author Index
