Language and Automata Theory and Applications
6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012, Proceedings
Published on 29. February 2012
XII, 556 pages
978-3-642-28332-1 (ISBN)
Description
This book constitutes the refereed proceedings of the 6th International Conference on Language and Automata Theory and Applications, LATA 2012, held in A Coruña, Spain in March 2012. The 41 revised full papers presented together with 3 invited talks and 2 invited tutorials were carefully reviewed and selected from 114 initial submissions. The volume features contributions from both classical theory fields and application areas; e.g. innformatics, systems biology, language technology, artificial intelligence, etc. 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
Language and Automata Theory and Applications
6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012, Proceedings
Book
02/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Talks
- Measuring Information in Timed Languages
- References
- Automata-Based Symbolic Representations of Polyhedra
- Introduction
- Basic Notions and Notations
- Polyhedra
- Topological Components
- Incidence Relation
- Extension to Polyhedral Partitions
- Towards a Better Data Structure for Polyhedra
- Real-Vector Automata
- Point Decision in RVA
- Principles of IRVA
- Decision Structure for Directions
- Implicit Real-Vector Automata
- Syntax
- Semantics
- Canonicity
- Canonical IRVA Representations
- Minimization Algorithm
- Combination Operation
- Conclusions and Perspectives
- References
- Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory
- The Church-Turing Thesis and Its Various Forms
- Why a Thesis?
- The Physical Church-Turing Thesis
- Beyond Natural Numbers
- Indexings
- Real Numbers
- Non-determinism
- Gandy's Proof
- Gandy's Hypotheses
- Gandy's Proof
- Criticizing Gandy's Hypotheses
- The Physical Church-Turing Thesis and the Galileo Thesis
- The Galileo Thesis
- The Physical Church-Turing Thesis Implies the Galileo Thesis
- An Algorithmic Description of the Laws of Nature
- A Property of Nature or of the Theory?
- The Physical Church-Turing Thesis and the Quantum Theory
- The Bounded Density of Information in the Quantum Case
- The Bounded Velocity of Information in the Quantum Case
- Conclusion
- References
- A Parameterized Complexity Tutorial
- Introduction
- Preamble
- The Idea
- Some Definitions
- Positive Techniques
- Bounded Search Trees
- Kernelization
- Iterative Compression
- Other Techniques
- Parametric Intractability
- XP-Optimality
- Other Things
- Left Out
- References
- The Computer Science of DNA Nanotechnology
- Regular Papers
- The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems
- Introduction
- Preliminaries
- Priced Timed Pushdown Systems
- From Priced to Unpriced Timed Pushdown Systems
- From Timed Pushdown Systems to Pushdown Systems
- Conclusion
- References
- Unification Modulo Chaining
- Introduction
- Notation and Preliminaries
- Inference System for BC-Unification
- Inference System INFl for List-Equations
- Solving a BC-Unification Problem
- BC1-Unification Is NP-Complete
- An Illustrative Example
- Conclusion
- References
- Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
- Introduction
- Main Result
- Approximate Isomorphism for ACs,d,n
- Exact Isomorphism Test for Low Degree Polynomials
- The Approximate Isomorphism Algorithm
- A General Approximate Isomorphism Algorithm
- References
- Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
- Introduction
- RTMs and RMFAs
- Reversible Turing Machines
- Reversible Multihead Finite Automata
- RMFAs Characterize Reversible Logspace
- Encoding an RTM Configuration
- Simulating RTM Transitions
- Simulating an RMFA with a Logarithmic Space RTM
- Further Discussion of RMFAs
- Conclusion
- References
- Defining Contexts in Context-Free Grammars
- Introduction
- Definition by Deduction
- Definition by Language Equations
- Normal Form
- Parsing Algorithm
- Recognition in Linear Space
- Future Work
- References
- Longest Common Extensions via Fingerprinting
- Introduction
- Preliminaries
- The [k] Algorithm
- Data Structure
- Query
- Preprocessing
- Experimental Results
- Tested Algorithms
- Test Inputs and Setup
- Results
- Cache Optimization
- Conclusions
- References
- Fast and Cache-Oblivious Dynamic Programming with Local Dependencies
- Introduction
- Memory Models
- Previous Results
- Our Results
- Basic Definitions
- A New Algorithm for LCS
- Computing Boundaries
- Computing the LCS
- Analysis
- Experimental Results
- Setup
- Results
- References
- An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings
- Introduction
- Preliminaries
- OBDDs and Functional Operations
- OBDD-Based Graph Algorithms and Matching Problems
- The Maximal Matching Algorithm
- Concluding Remarks
- References
- Strong Termination for Gap-Order Constraint Abstractions of Counter Systems
- Introduction
- Preliminaries
- Properties of Monotonicity Graphs
- Results on the Reachability Relation in GCS
- Strong Termination for Simple GCS
- S Satisfies the Termination Condition
- Strong Termination for Unrestricted GCS
- References
- Covering Space in the Besicovitch Topology
- Introduction
- Definitions and Tools
- Toeplitz Configurations and Their Construction
- The Result for the General Case
- Quasiperiodic Case Study
- Regular Toeplitz Case Study
- Finite Words and the Hamming Distance
- Result for Regular Toeplitz Configurations
- Bound Tightness for Regular Toeplitz Configurations
- References
- Approximate Regular Expressions and Their Derivatives
- Introduction
- Preliminaries
- Comparison Functions: Symbols, Sequences and Words
- Word Comparison Functions, Quotients and Derivatives
- Quotient of an Fk(L) Language
- Brzozowski Derivatives
- Antimirov Derivatives
- Conclusion
- References
- Catalytic Petri Nets Are Turing Complete
- Introduction
- Petri Nets and Firing Strategies
- Membrane Systems with Catalysts
- Relating Petri Nets and Membrane Systems
- Catalytic Petri Nets Are Turing Complete
- Conclusion and Future Work
- References
- Computational Complexity of Rule Distributions of Non-uniform Cellular Automata
- Introduction
- Notations and Definitions
- Number Conservation
- Surjectivity and Injectivity
- Equicontinuity and Sensitivity for Linear r-CA
- Conclusions
- References
- Conservative Groupoids Recognize Only Regular Languages
- Introduction
- Conservative Groupoids and Tournaments
- Commutative Case
- Building the Grammar
- Correctness of the Grammar
- Completeness of the Grammar
- Regularity of the Language Generated by the Grammar
- Non-commutative Case
- Building the Grammar
- Regularity of the Language Generated by the Grammar
- Languages Recognized by Conservative Groupoids
- Conclusion and Future Work
- References
- Advice Complexity of Online Coloring for Paths
- Overview of Advice Complexity
- Definitions
- Advice Complexity Definitions
- Online Coloring Definitions
- Theorems
- Proof of Theorem 1
- Proof of Theorem 2
- Conclusion
- References
- A Faster Grammar-Based Self-index
- Introduction
- Adding Bookmarks to a Balanced SLP
- Listing Occurrences
- Postscript
- References
- Learnability of Co-r.e. Classes
- Introduction
- Learnability
- Characterisations of Conservative Learning
- Indexed Families of Recursive Sets
- General Classes of r.e. Sets, Co-r.e. Sets, and Separations
- Conclusion
- References
- Two-Way Automata Making Choices Only at the Endmarkers
- Introduction
- Preliminaries
- The Subroutine Reach
- Simulation by Halting Self-verifying Automata
- Subexponential Deterministic Simulation
- Conditional and Unambiguous Simulations
- The Alternating Case
- Concluding Remarks
- References
- Polynomial-Time Algorithms for Learning Typed Pattern Languages
- Introduction
- Preliminaries and Background
- Pattern Languages and Typed Pattern Languages
- Learnability
- Type Witnesses
- Polynomial-Time Learning of Typed Pattern Languages
- Extensions of the Presented Results
- Learning Typed Pattern Languages over Infinitely Many Types
- Consistent Learning of Typed Pattern Languages
- Conclusion
- References
- Forbidding Sets and Normal Forms for Language Forbidding-Enforcing Systems
- Introduction
- Language Forbidding-Enforcing Systems
- Subword-Free and Subword-Incomparable Normal Forms
- Connecting Words and Minimal Normal Form
- Normal Forms for Strict Forbidding Sets
- Concluding Remarks
- References
- Applying Tree Languages in Proof Theory
- Introduction
- Rigid Tree Languages
- From Proofs to Tree Languages
- From Tree Languages to Proofs
- Applications
- Conclusion
- References
- The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
- Introduction
- Regular Expressions with Unordered Concatenation and Numerical Constraints
- Complexity of Membership under Unordered Concatenation
- Term Trees, Positions, and Subscripting
- Finite Automata with Counters
- Finite Automata with Counters
- Word Recognition
- Unambiguity
- Related Work
- Conclusion
- References
- Characterizing the Rational Functions by Restarting Transducers
- Introduction
- Restarting Transducer with Window Size One
- Restarting Automata with Window Size One
- Restarting Transducer
- Examples of Functions Computed by RR(1)-Transducers
- Relations Computed by nf-RR(1)-Transducers
- Sequential and Rational Functions
- Concluding Remarks
- References
- Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines
- Introduction
- Preliminaries
- Weak Synchronization of Multitape Automata
- Technique 1: Simulation by 1NPDAs with Reversal-Bounded Counters
- Technique 2: Reduction from Post Correspondence Problem
- Technique 3: Reduction from Halting Problems
- Space-Bounded Multitape Turing Machines
- Summary
- References
- Feasible Automata for Two-Variable Logic with Successor on Data Words
- Introduction
- Notation
- Weak Data Automata
- A Logical Characterization of Weak Data Automata
- From Weak Data Automata to EMSO2(+1,)
- From EMSO2(+1,) to Weak Data Automata
- Weak Büchi Data Automata
- Conclusion
- References
- Nash Equilibria in Concurrent Priced Games
- Introduction
- Preliminaries
- Temptation and Punishment
- Equilibrium Automaton
- Complexity of the Decision Variant
- Conclusion
- References
- Computing by Observing Insertion
- Computing by Observing
- Insertion Observer Systems
- Insertion Systems
- Observers
- Insertion Observer Systems
- Computing by Observing Insertion Systems
- Observing only Change
- Conclusions
- References
- On the Parameterized Complexity of Default Logic and Autoepistemic Logic
- Introduction
- Preliminaries
- MSO-Encodings
- Default Logic
- Autoepistemic Logic
- Pseudo-cliques
- Conclusion
- References
- Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic
- Introduction
- Cayley Graph Automatic and Cayley Graph Biautomatic Groups
- (Free-abelian)-by-free Groups with Undecidable Conjugacy Problem
- References
- On Model Checking for Visibly Pushdown Automata
- Introduction
- Visibly Pushdown Automata
- Definitions
- Universality and Inclusion Checking
- Emptiness Checking
- Universality Checking
- Inclusion Checking
- Implementation and Experiments
- Conclusion
- References
- Automaton-Based Array Initialization Analysis
- Introduction
- A Simple Imperative Language and Its Semantics
- Regular Trace Approximation
- The Static Analysis Algorithm
- Dealing with Implicit Upper Bounds and Side-Effects
- Experiments
- Conclusion
- References
- Dynamics of Circuits and Intersecting Circuits
- Definitions and Preliminary Results
- Main Result
- Comparisons and Bounds
- Conclusion
- References
- Canonizable Partial Order Generators
- Introduction
- Transitive Reduction of Slice Graphs and Its Consequences
- Slices
- Sliced Transitive Reduction
- References
- Ogden's Lemma for ET0L Languages
- Introduction
- Definitions
- Previous Work
- Main Results
- Applications
- Concluding Remarks
- References
- Patterns with Bounded Treewidth
- Introduction
- Preliminaries
- Patterns and Words as Relational Structures
- Patterns with Restricted Scope Coincidence Degree
- References
- P-NP Threshold for Synchronizing Road Coloring
- Introduction
- Preliminaries
- SRCPC3 Is NP-complete for C 4 and 3
- Complexity of SRCPC for C=1,2 and 1
- Conclusions and Future Work
- References
- k-Automatic Sets of Rational Numbers
- Introduction
- Representing Rational Numbers
- Examples
- Basic Results
- Solvability Results
- References
- On Stable and Unstable Limit Sets of Finite Families of Cellular Automata
- Introduction
- Definitions
- Limit Sets and Basic Results
- Hierarchies
- Boolean Operations
- Conclusions
- References
- Automaton Ranks of Some Self-similar Groups
- Introduction
- Self-similar Groups and Their Automaton Ranks
- The Language of Wreath Products
- Automaton Groups and Automaton Ranks
- Automaton Ranks of Free Abelian Groups
- The Groups .HH as Automaton Groups
- The Case of Alternating Groups An, n&4
- The Case H=PSL2(p), p&3
- References
- One-Way Reversible and Quantum Finite Automata with Advice
- Background, Motivations, and Challenges
- Basic Terminology
- Reversible Finite Automata with Advice
- Properties of Advice for Quantum Computation
- References
- Integration of the Dual Approaches in the Distributional Learning of Context-Free Grammars
- Introduction
- Preliminaries
- Learning Targets
- Hypotheses
- Construction
- Properties of Hypotheses
- Learning of G(p,q,r)
- Identification in the Limit from Positive Data and Membership Queries
- Learning Algorithm for G(p,q,r)
- Learning of G(r)
- Minimally Adequate Teacher
- Learning Algorithm for G(r)
- Concluding Remarks
- References
- Author Index
