Implementation and Application of Automata

Name: Implementation and Application of Automata | 16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011, Revised Selected Papers

Béatrice Bouchou-Markhoff Pascal Caron Jean-Marc Champarnaud Denis Maurel(Herausgeber*in)

Springer (Verlag)

Erschienen am 5. Juli 2011

XIII, 299 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22256-6 (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 Lectures
Derick Wood: Always in Our Hearts
References
Streamable Fragments of Forward XPath
Introduction
FXP
Deterministic Automata for XML Streams
FXP to Deterministic Automata
Streamability of Query Languages
Related Work
Conclusion
References
Gaining Power by Input Operations: Finite Automata and Beyond
Introduction
Extended Finite Automata
Computational Capacity
Extended Pushdown Automata
Conclusions
References
Technical Contributions
Weak Inclusion for XML Types
Introduction
Preliminaries
Weak Inclusion for Regular Tree Grammars
Experimental Results
The Special Case of Deterministic DTDs
Conclusion
References
Categorial Grammars with Iterated Types form a Strict Hierarchy of k-Valued Languages
Introduction
Background
Categorial Grammars
*AB Calculus
Abstract Automata Equivalent to CDG
Deduction Structures
F-A Structures over a Set E
Functor-Argument Structures with Iterated Subtypes
A Strict Hierarchy
Overview
Order 1 and Iteration
Order &1 and Iteration
Conclusion
References
Bouma2 - A High-Performance Input-Aware Multiple String-Match Algorithm
Introduction
Related Work
Basic Definitions
Traces and Motifs
Resolve-Sets
The Bouma2 Compilation Process
Cost Functions
The Bouma2 Compilation Graph
The Bouma2 Match Process
The Match Structures
Match-Time Algorithm
The Resolve Process
The Resolve Dimension
Experimental Results
Extensions and Future Work
References
Random Generation of Deterministic Acyclic Automata Using Markov Chains
Introduction
Notations
Markov Chains and Random Generation
Algorithm
Proofs
Minimal Acyclic Automata
Experiments
Conclusion
References
Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability
Introduction
Definitions
Satisfiability as FSA Construction
Variable and Clause Ordering Heuristics
Experimentation
Tool and Setting
Initial Experiments
Hard Benchmarks Experiments
Conclusions and Future Work
References
Nondeterministic Moore Automata and Brzozowski's Algorithm
Introduction
Nondeterministic Moore Automata
A Variant of Brzozowski's Algorithm on Nondeterministic Moore Automata
Conclusions and Further work
References
Building Phylogeny with Minimal Absent Words
Introduction
Basic Definition
Method
Minimal Absent Words Trie Computation
Similarity/Dissimilarity Measures
Results and Discussion
Minimal Absent Words Trie Computation
Phylogeny Building from Minimal Absent Words
Conclusion
References
On the Hardness of Priority Synthesis
Introduction
Example: Simple BIP Models
Formulating BIP Models and Priority Synthesis Based on Transition Systems
Priority Synthesis Is NP-Complete
Discussion
References
Smaller Representation of Finite State Automata
Introduction
Motivation and Goals
Test Data
Size Reduction Techniques
Experiments and Results
Conclusions
References
Compositional Failure Detection in Structured Transition Systems
Introduction
Technical Preliminaries
Products of Transition Systems
Automata
Composition: Simple Case
Extension to Specifications with Predicates
Further Results and Conclusion
References
Chrobak Normal Form Revisited, with Applications
Introduction
Preliminaries
The Algorithm
Application to Regular Expressions Conversion
Application to Context-Free Grammar Conversion
References
A Cellular Automaton Model for Car Traffic with a Form-One-Lane Rule
Introduction
CA-Based Traffic Simulation Models
Form-One-Lane Rule Model
Experiments and Analysis
Single-Lane Model and the Proposed Model
The Traffic Flux with a Junction
The Length of Traffic Jam
Applications of the Proposed Model
Conclusions
References
Loops and Overloops for Tree Walking Automata
Introduction
Loops, Overloops and the Membership Problem
Transforming TWA into Equivalent BUTA
Two Variants: Loops and Overloops
Overloops and the Deterministic Case
The Emptiness Problem and Experimental Results
Conclusion
References
Nondeterministic State Complexity of Star-Free Languages
Introduction
Preliminaries
Results on the Operation Problem
References
On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs
Introduction
Undecidability of Containment and Equivalence
Output Finite-Valued NFTs
Right-Bounded LCFGs
Output/Input Finite-Valued NFTs
Right/Left-Bounded LCFGs
Generalizations
References
Computing All l-Cover Automata Fast
Introduction
Preliminaries
Gap-Trees
Computing a Gap-Tree
References
Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines
Towards More Expressive 2D Deterministic Automata
Introduction
Preliminaries
Tiling Recognizable Picture Languages
2D Automata Models
Adding Expressivity
Properties of 4-Way Deterministic Wang Automata
References
Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata
Introduction
Cyclic Automata
Eulerian Automata
Conclusion and Conjectures
References
Distributed Event Clock Automata
Introduction
Preliminaries
Models of Time
Clo cks
Automata Background
Timed Automata
Timed Automata with Independent Clocks
Recursive Event Clocks Automata
Timed Languages
Timed Languages of icTA
Distributed Event Clock Automata
Timed Languages of DECA
Recursive Distributed Event Clocks Temporal Logic
Syntax
Semantics
Decidability
Extensions
Conclusions
References
Short Papers
Fly-Automata, Their Properties and Applications
Introduction
Preliminaries: Terms
Application Domain
Graphs as Logical Structures
Term Representation of Graphs of Bounded Clique-Width
Term Automata
Finite Bottom-Up Term Automata
Infinite (Bottom-up) Term Automata
Fly Term Automata
Implementation of Fly-Automata
Experiments
Conclusion and Perspectives
References
Tree Template Matching in Ranked Ordered Trees by Pushdown Automata
Introduction
Preliminaries
Basic Definitions
Properties of Trees in Postfix Notation
Problem Definition
Algorithm
Match-Sets
Computing Match-Sets
The Algorithm
Conclusion
References
Information Extraction from Semi-structured Resources: A Two-Phase Finite State Transducers Approach
Introduction
Finite State Transducers in NLP
Resources and Tools Used
Software System for Linguistic Tasks
Semi-structured Resource: Encyclopedia
The Two Phase FST Method
The First Phase: Creating Records of Data
The Second Phase: Extracting Particular Attributes
Results and Evaluation of the Method
Conclusion
References
Experimental Study of the Shortest Reset Word of Random Automata
Introduction
Solving Automata Synchronization Problem via Reduction to SAT
Random Automaton
Experimental Results
Conclusion and Discussion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken