Developments in Language Theory
16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012, Proceedings
Published on 16. July 2012
XIII, 478 pages
978-3-642-31653-1 (ISBN)
Description
This book constitutes the refereed proceedings of the 16th International Conference on Developments in Language Theory, DLT 2012, held in Taipei, Taiwan, in August 2012.
The 34 regular papers presented were carefully reviewed and selected from numerous submissions. The volume also contains the papers or extended abstracts of 4 invited lectures, as well as a special memorial presentation in honor of Sheng Yu. The topics covered include grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; algorithmic, combinatorial and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular automata; polyominoes and multidimensional patterns; decidability questions; image manipulation and compression; efficient text algorithms; relationships to cryptography, concurrency, complexity theory and logic; bio-inspired computing; quantum computing.
The 34 regular papers presented were carefully reviewed and selected from numerous submissions. The volume also contains the papers or extended abstracts of 4 invited lectures, as well as a special memorial presentation in honor of Sheng Yu. The topics covered include grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; algorithmic, combinatorial and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular automata; polyominoes and multidimensional patterns; decidability questions; image manipulation and compression; efficient text algorithms; relationships to cryptography, concurrency, complexity theory and logic; bio-inspired computing; quantum computing.
More details
Other editions
Additional editions
Hsu-Chun Yen | Oscar H. Ibarra
Developments in Language Theory
16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012, Proceedings
Book
07/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Talks
- The Kind Hearted Dragon Prof. Sheng Yu, 1950-2012
- References
- P and dP Automata: Unconventional versus Classical Automata
- Introduction
- Preliminaries
- P Automata
- Discussion of Features of P Automata
- Accepting Power of P Automata
- dP Automata
- Accepting Power of dP Automata
- Multi-head Finite Automata versus Finite dP Automata
- Conclusions
- References
- Recovering Strings in Oracles: Quantum and Classic
- Determinism vs. Nondeterminism for Two-Way Automata
- Introduction
- Liveness Problems
- Reasonable Automata
- Main Results
- Lower Bounds
- Upper Bounds
- Conclusion
- References
- Cellular Automata, the Collatz Conjecture and Powers of 3/2
- Introduction
- Definitions
- A Universal Pattern Generator
- Strong Pattern Generation
- Relation to Some Open Problems in Number Theory
- Mahler's Z-Numbers
- Collatz Function
- Concluding Remarks
- References
- Regular Papers
- Quotient Complexities of Atoms of Regular Languages
- Introduction
- Upper Bounds on the Quotient Complexities of Atoms
- Automata and Átomata of Regular Languages
- The Witness Languages and Automata
- Tightness of the Upper Bounds
- Conclusions
- References
- Decidability of Geometricity of Regular Languages
- Introduction
- Geometrical Languages
- Semilinear Sets
- Regular Geometrical Languages
- References
- Inside the Class of REGEX Languages
- Introduction
- General Definitions
- Patterns with Regular Operators and Types
- Pattern Expressions
- REGEX
- REGEX with a Bounded Number of Backreferences
- References
- Computing the Edit-Distance between a Regular Language and a Context-Free Language
- Introduction
- Preliminaries
- Edit-Distance
- The Edit-Distance between an RL and a CFL
- Alignment PDA
- Computing an Optimal Alignment from A(A,P)
- Edit-Distance and Unary Homomorphism
- References
- Semigroups with a Context-Free Word Problem
- Introduction
- Preliminaries
- Semigroups with Context-Free Word Problem
- Finite Rees Index
- Completely Simple Semigroups
- Rational Semigroups and Linear World Problems
- References
- Generalized Derivations with Synchronized Context-Free Grammars
- Introduction
- Preliminaries
- Transducer Synchronization
- Unary Transducers
- References
- Non-erasing Variants of the Chomsky-Sch¨utzenberger Theorem
- Introduction
- Normal Form
- Homomorphic Characterization of Even-Length Languages
- Characterizations
- Concluding Remarks
- References
- Regular and Context-Free Pattern Languages over Small Alphabets
- Introduction
- Definitions and Known Results
- Regularity and Context-Freeness of Pattern Languages: Sufficient Conditions and Necessary Conditions
- Regularity of E-Pattern Languages: A Sufficient Condition Taking Terminal Symbols into Account
- References
- On Context-Free Languages of Scattered Words
- Introduction
- Basic Notions
- Linear Orderings
- Words and Languages
- Linear Context-Free Languages
- Context-Free Languages of Scattered Words of Bounded Rank
- Operational Characterization of BCFLs of Scattered Words
- An Application
- Future Research
- References
- Homomorphisms Preserving Deterministic Context-Free Languages
- Introduction
- Context-Free Languages and Their Special Cases
- Codes and Their Deciphering Delay
- Codes Preserving Deterministic and LL Context-Free Languages
- Non-codes Preserving Deterministic and LL Context-Free Languages
- References
- Unary Coded NP-Complete Languages in ASPACE (log log n)
- Introduction
- Preliminaries
- Encoding Boolean Formulas
- Encoded 3-Satisfiability
- Conclusion
- References
- Dense Completeness
- Introduction
- Preliminaries
- The Context-Free Languages and the Class SAC1
- The One-Counter Languages and the Class NL
- The Indexed Languages and the Class NP
- The Regular Languages and the Class NC1
- Discussion
- References
- From Equivalence to Almost-Equivalence, and Beyond-Minimizing Automata with Errors
- Introduction
- Preliminaries
- Finite Automata Equivalence, Minimization, and Related Problems
- Equivalence Problems
- Canonical Languages
- Minimization Problems
- Deciding Minimality
- Counting Minimal Automata
- References
- Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata
- Introduction
- Preparation
- Nondeterministic Finite Automata
- Monadic Second-Order Logic with Successor
- Existential Anchor-Slide Sentences
- From Automata to Formulas
- From Formulas to Automata
- Conclusion
- References
- States and Heads Do Count for Unary Multi-head Finite Automata
- Introduction
- Preliminaries and Definitions
- State and Head Double Hierarchy
- Head Hierarchy for Stateless Finite Automata
- Four States Are Too Much for Two-Head Automata
- References
- Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness
- Introduction
- Definitions
- Preliminaries
- Visibly Pushdown Automata with Multiplicities
- Relating Tree Automata and VPA
- Characterization and Decision of Infinite N-VPA
- Characterization
- Decidability of Finiteness
- Finite Bounds for N-VPA
- Deciding K-Bounded Multiplicity
- Deciding K-Bounded Multiplicity (for a Fixed K)
- Back to Trees
- References
- Unambiguous Constrained Automata
- Introduction
- Preliminaries
- Closure Properties and Expressiveness of UnCA
- Decision Problems for UnCA
- A Deterministic Form of UnCA
- Conclusion
- References
- Two-Dimensional Sgraffito Automata
- Introduction
- Preliminaries
- Sgraffito Automata
- Closure Properties
- A Taxonomy of Picture Languages
- Conclusions
- References
- Two-Way Transducers with a Two-Way Output Tape
- Introduction
- Two-Way Transducers
- Rational Relations and One-Way Transducers
- Special Case
- Deterministic Two-Way Transducers
- Conclusion
- References
- Learning Rational Functions
- Introduction
- Rational Functions
- Transducers with Look-Ahead
- Building the Look-Ahead Automaton
- The Learning Algorithm
- Characteristic Samples
- References
- Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata
- Introduction
- Preliminaries
- From NFAs to Parikh Equivalent DFAs
- From CFGs to Parikh Equivalent DFAs
- Conclusion
- References
- Fine and Wilf 's Theorem for k-Abelian Periods
- Introduction
- Preliminaries
- Existence of Bounds
- Initial 2-Abelian Periods
- General Upper Bounds
- Conclusion
- References
- Pseudoperiodic Words
- Introduction
- Definitions and Notation
- Words
- Permutations
- Pseudopalindromes
- Generalized Pseudostandard Words
- Pseudoperiodicity
- Graphs
- Fine and Wilf's Theorem
- Pseudocentral Words
- Concluding Remarks and Future Work
- References
- Acceptance Conditions for $\omega$-Languages
- Introduction
- Notations and Background
- The Accepting Conditions A and A and the Borel Hierarchy
- The Accepting Conditions (ninf,) and (ninf,)
- Towards a Characterization of (fin, =) and (fin,)
- Conclusions
- References
- Checking Determinism of Regular Expressions with Counting
- Introduction
- Preliminaries
- Computing followlast Sets
- Properties of Expressions in RE(#)
- Strong Determinism
- Adaption to Weak Determinism
- The Local Nondeterminism-Locating Feature and Discussion
- References
- Biautomata for k-Piecewise Testable Languages
- Introduction
- Preliminaries
- Piecewise Testable Languages and Syntactic Monoids
- Biautomata for Piecewise Testable Languages
- Proof of the Theorem
- Estimates Using J-Trivial Monoids
- Concluding Remarks
- References
- On Centralized PC Grammar Systems with Context-Sensitive Components
- Introduction
- The Complexity Classes NSPACE(n) and NEXT
- Centralized PC Grammar Systems
- String-Rewriting Systems
- The Main Result
- Concluding Remarks
- References
- Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars
- Introduction
- Preliminaries
- Synchronous Tree-Adjoining Grammars
- Relating STAG and XTOP
- Bimorphism Semantics
- Relating STAG and XTOP, Again
- Results
- References
- The State Complexity of Star-Complement-Star
- Introduction
- Upper Bound
- Lower Bound
- Applications
- References
- On State Complexity of Finite Word and Tree Languages
- Introduction
- Preliminaries
- Finite Language with Bounded Word Length
- Union and Intersection of Finite Languages
- Tree Automata and Tree Languages
- References
- Squares in Binary Partial Words
- Introduction
- Square Positions
- Square Occurrences
- Distinct Squares
- Conclusion
- References
- The Avoidability of Cubes under Permutations
- Introduction
- Preliminaries
- The Morphic Case
- The Antimorphic Case
- Conclusions
- References
- Hairpin Completion with Bounded Stem-Loop
- Introduction and Preliminaries
- Pseudopalindromic Regular Languages
- Iterated Pseudopalindromic Completion
- Decidability Questions
- References
- Morphic Primitivity and Alphabet Reductions
- Introduction
- Definitions
- Unambiguous Alphabet Reductions
- Alphabet Reductions Preserving Morphic Primitivity
- References
- Short Papers
- On a Hierarchy of Languages with Catenation and Shuffle
- Introduction
- Definitions and Basic Structures
- Basic Structures
- Systems of Equations
- Algebraic Closures
- Normal Forms
- Hierarchies
- The Lower Hierarchy
- The Upper Hierarchy
- Outlook
- References
- Characterizing Languages by Normalization and Termination in String Rewriting
- Motivation
- Preliminaries
- Sets of Strings with Alphabet Extension
- Reducing the Alphabet to
- Complexity of Languages Characterizable in
- Conclusion and Future Work
- References
- Geometry and Dynamics of the Besicovitch and Weyl Spaces
- Introduction
- Definitions
- Sofic Shifts and Simplicial Complexes
- CA-Like Functions and B-Nontransitivity of CA
- References
- A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
- Preliminaries: Codes and Transducers
- Generalization of Girod's Method to f.d.d. Codes
- Transducers for Decoding
- A Remarkable Strongly Connected Component
- References
- Author Index
