Language and Automata Theory and Applications

Name: Language and Automata Theory and Applications | 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011

Adrian-Horia Dediu Carlos Martín-Vide Shunsuke Inenaga(Herausgeber*in)

Springer (Verlag)

Erschienen am 27. Mai 2011

XIII, 512 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-21254-3 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken