Implementation and Application of Automata
17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings
Published on 27. August 2012
XIII, 369 pages
978-3-642-31606-7 (ISBN)
Description
This book constitutes the thoroughly refereed papers of the 17th International Conference on Implementation and Application of Automata, CIAA 2012, held in Porto, Portugal, in July 2012. The 21 revised full papers presented together with 5 invited papers and 7 short papers were carefully selected from 53 submissions. The papers cover various topics such as automata applications in formal verification methods, natural language processing, pattern matching, data storage and retrieval, and bioinformatics, as well as theoretical work on automata theory.
More details
Other editions
Additional editions
Nelma Moreira | Rogério Reis
Implementation and Application of Automata
17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings
Book
07/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Talks
- In Memoriam Sheng Yu
- References
- In Search of Most Complex Regular Languages
- Introduction
- Conditions for the Complexity of Languages
- Properties of a Single Language
- Unary Operations
- Binary Operations
- The Witness
- Properties of a Single Language
- Unary Operations
- Binary Operations
- Boolean Operations
- Product
- Combined Operations with Um(a,b,c) and Un(b,a,c)
- Combined Operations with ``Dialects'' of Un(a,b,c)
- Witnesses Over Quaternary Alphabets
- Witnesses Un(a,b,c,d) and U"0362Un(a,b,c,d)
- Witnesses Vn(a,b,c,d) and V"0362Vn(a,b,c,d)
- Witnesses Wn(a,b,c,d) and W"0362Wn(a,b,c,d)
- Conclusions
- References
- A Formal Framework for Processes Inspired by the Functioning of Living Cells
- References
- Adding Pebbles to Weighted Automata
- Introduction
- Motivations
- Language Modeling
- Weighted Linear Temporal Logic
- Preliminaries
- Weighted Expressions with Pebbles
- Series Over a Partial Monoid
- Weighted Automata with Pebbles
- From Automata to Expressions
- Generalized Pebble Automata
- Automata to Expressions: 0-layered Generalized pebWA
- Automata to Expressions: Generalized pebWA
- From Expressions to Automata
- Evaluation of Pebble Weighted Automata
- Discussion
- References
- Typed Linear Algebra for Weigthed (Probabilistic) Automata
- Introduction
- Typed Linear Algebra
- Weighted Automata as MatS Arrows
- Weighted Automata Homomorphisms
- Summary
- Current and Related Work
- References
- Regular Papers
- A Pushdown Transducer Extension for the OpenFst Library
- Introduction
- Definitions
- Dyck Languages
- Pushdown Automata and Transducers
- Implementation
- Algorithms
- Expansion
- Composition
- Shortest Distance and Shortest Path
- Pruned Expansion
- Replacement
- Discussion
- Applications
- Recognition
- Parsing
- Translation
- Discussion
- References
- Weak Inclusion for Recursive XML Types
- Introduction
- Preliminaries
- Weak Inclusion for Possibly-Recursive Tree Grammars
- Implementation and Experiments
- Related Work and Discussion
- References
- Synchronizing Automata on Quasi-Eulerian Digraph
- Synchronizing Automata and the Cerný Conjecture
- Exponents of Primitive Matrices vs. Reset Lengths
- Markov Chains and a New Extension Method
- Quasi-Eulerian Automata
- References
- Cellular Automata on Regular Rooted Trees
- Introduction
- Definitions and Background
- The Free Monoid *
- Configurations and Tree Shifts
- Forbidden Blocks and Shifts of Finite Type
- Cellular Automata and Sofic Tree Shifts
- Unrestricted Rabin Graphs and Automata
- Graphical Representation
- Unrestricted Rabin Automata and Sofic Shifts
- Deterministic and Co-deterministic Presentations
- Full-Tree-Patterns and Finite-Tree Automata
- Finite-Tree Automata
- References
- Strict Local Testability with Consensus Equals Regularity
- Introduction
- First Definitions and Properties
- Consensual Languages with Regular and Subregular Bases
- Consensual Languages over Non-regular Bases
- Conclusion
- References
- Nominal Automata for Resource Usage Control
- Preliminaries
- Usages
- Usage Automata
- Variable Finite Automata on Data Words
- Properties of Usages and UA
- Model Checking
- References
- Weighted Nested Word Automata and Logics over Strong Bimonoids
- Introduction
- Strong Bimonoids
- Nested Words and Weighted Nested Word Automata
- Weighted Logics on Nested Words
- Conclusion
- References
- A Fast Suffix Automata Based Algorithm for Exact Online String Matching
- Introduction
- Basic Notions and Definitions
- Previous Efficient Suffix Automaton Based Solutions
- A New Fast Suffix Automaton Based Algorithm
- Experimental Results
- Conclusions and Future Works
- References
- P(l)aying for Synchronization
- Introduction and Overview
- Playing for Synchronization
- Paying for Synchronization
- Open Problems
- References
- Synchronizing Automata of Bounded Rank
- Introduction
- Preliminaries
- Main Results
- Conclusion and Discussion
- References
- Automatic Theorem-Proving in Combinatorics on Words
- Introduction
- The Decision Procedure
- Borders
- Additional Results on Unbordered Words
- Other Problems
- Open Problems
- References
- How to Synchronize the Heads of a Multitape Automaton
- Introduction
- Preliminaries
- Synchronizabilty of Multitape NPDAs
- Synchronizability of 2-Tape NFAs with 1-Reversal Counters
- Conclusions
- References
- Regular Ideal Languages and Their Boolean Combinations
- Introduction
- Preliminaries
- Ideals and Their Boolean Combinations
- One-Way Automaton Models
- Two-Way Automaton Models and Languages in DA
- References
- Hyper-minimization for Deterministic Tree Automata
- Introduction
- Preliminaries
- Hyper-minimal Automata
- Hyper-minimization
- Discussion
- References
- On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
- Introduction
- Preliminaries and Definitions
- Main Results
- Conclusions
- References
- Implementing Computations in Automaton (Semi)groups
- Introduction
- Automaton (Semi)groups
- Mealy Automaton
- Generating (Semi)groups
- Minimization and the Word Problem
- Fully Exploiting the Minimization
- Growth
- Order of the (Semi)group
- Finiteness
- Conjectures
- References
- On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
- Introduction
- Notation and Definitions
- Descriptional Complexity
- A Semi-Thue System for Turing Machine Histories
- The Descriptional Impact of the Window Size
- Conclusion
- References
- A Disambiguation Algorithm for Finite Automata and Functional Transducers
- Introduction
- Preliminaries
- Disambiguation Algorithm for Finite Automata
- Description
- Analysis
- Disambiguation of Automata with -Transitions
- Disambiguation of Finite-State Transducers
- Conclusion
- References
- Synchronization of Automata with One Undefined or Ambiguous Transition
- Introduction
- Classes of Automata and Computational Problems
- Automata with One Undefined Transition
- Automata with One Ambiguous Transition
- Automata with Binary Alphabet
- References
- Restarting Tiling Automata
- Introduction
- Basic Definitions
- Two-Dimensional Restarting Tiling Automata
- Two-Dimensional Bounded Turing Machines and 2RTAs
- 2RTA Working over One-Row Pictures
- Conclusions
- References
- Crossing the Syntactic Barrier: Hom-Disequalities for H1-Clauses
- Introduction
- Preliminaries
- Expressiveness
- Automata with Hom-Disequalities
- H1-Normalization
- Conclusion
- References
- Short Papers
- Factor and Subsequence Kernels and Signatures of Rational Languages
- Introduction
- Basic Notions and Definitions
- Weighted Automata
- Weighted Transducers
- Rational Kernel of Languages and Signatures
- Factor Signature
- Factor Signature of Words
- Factor Signature of Languages
- Subsequence Signature and Kernel
- Subsequence Signature of Words
- Subsequence Signature of Languages
- Direct Computation of the Automaton Realizing the Subsequence Signature
- References
- Multi-Tilde-Bar Derivatives
- Introduction
- Preliminaries
- Quotient Formulae
- Word Derivatives of an EMRE
- Partial Derivatives of an EMRE
- Conclusion
- References
- On Positive TAGED with a Bounded Number of Constraints
- Introduction
- Preliminaries
- The Emptiness and Finiteness Problems
- The Membership Problem
- Conclusions
- References
- SDFA: Series DFA for Memory-Efficient Regular Expression Matching
- Introduction
- Related Work
- Technical Overview of Series DFA
- State Complexity for RegExes
- Main Idea of SDFA
- Optimization for Series DFA
- Optimization in Cutting Process
- Optimization in Matching Process
- Experimental Results
- Evaluation of Memory Consumption
- Evaluation of Matching Performance
- References
- The Removal of Weighted e-Transitions
- Valid Weighted Automata
- The Weighted Closure Algorithm
- Decision Algorithm
- The Case of Topological Ordered Positive Semirings
- The Case of R and Q
- References
- Weighted LTL with Discounting
- Introduction
- Preliminaries
- Weighted Generalized Büchi Automata with Discounting and -Transitions
- Results
- Conclusion
- References
- Automata with Modulo Counters and Nondeterministic Counter Bounds
- Introduction
- Definitions
- Expressive Power, Hierarchy and Decidability
- without States
- References
- Author Index
