Implementation and Application of Automata

Name: Implementation and Application of Automata | 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings

Nelma Moreira Rogério Reis(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 27. August 2012

XIII, 369 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31606-7 (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
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

Systemvoraussetzungen

Als PDF speichern Als Link merken