Implementation and Application of Automata

10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers

Jacques Farré, Igor Litovsky, Sylvain Schmitz (Herausgeber)

Buch | Softcover

XIII, 360 Seiten

2006
Springer Berlin (Verlag)
978-3-540-31023-5 (ISBN)

Artikel merken

The 10th International Conference on Implementation and Application of - tomata (CIAA 2005)washeld in the Technopole of Sophia Antipolis, France, on June 27 29, 2005. This volume of the Lecture Notes in Computer Science series contains the notes of the two invited lectures, the 26 papers selected for presentation at the conference, and the abstracts of the eight posters that were displayed. The papers and posters were selected amongst 87 submitted papers. The submissions came from countries in ?ve continents. They show applications of automata in many ?elds, including mathematics, linguistics, networks, XML processing,biologyand music. The elderly lady of automata is aliveand kicking, ready to face the new challenges of computer science. Based on the reviews, the Best Paper Award was given to Markus Lohrey and Sebastian Maneth for their excellent article on Tree Automata and XPath on Compressed Trees (see page 225). This award was generously sponsored by the University of California at Santa Barbara. We wish to thank all the Program Committee members and the additional referees for their e?orts in refereeing and selecting papers, and maintaining the high standard of CIAA conferences. We are grateful to all the contributors to the conference, in particular to the invited speakers, for making CIAA 2005 a scienti?c success. We also thank the Computer Science Department of the EcolePolytechnique Universitaire of the University of Nice - Sophia Antipolis for accommodating CIAA in its buildings and providing the logistical support.

Invited Lectures.- Languages Recognizable by Quantum Finite Automata.- The Language, the Expression, and the (Small) Automaton.- Technical Contributions.- Minimization of Non-deterministic Automata with Large Alphabets.- Simulating Two-Dimensional Recognizability by Pushdown and Queue Automata.- Component Composition Preserving Behavioural Contracts Based on Communication Traces.- Strong Retiming Equivalence of Synchronous Schemes.- Prime Normal Form and Equivalence of Simple Grammars.- An Incremental Algorithm for Constructing Minimal Deterministic Finite Cover Automata.- Finite Automata and Unions of Regular Patterns with Bounded Constant Segments.- Inside Vaucanson.- Deterministic Recognition of Trees Accepted by a Linear Pushdown Tree Automaton.- Shorter Regular Expressions from Finite-State Automata.- Wind in the Willows - Generating Music by Means of Tree Transducers.- On Deterministic Catalytic Systems.- Restricting the Use of Auxiliary Symbols for Restarting Automata.- A Class of Rational n-WFSM Auto-intersections.- Experiments with Deterministic ?-Automata for Formulas of Linear Temporal Logic.- Computing Affine Hulls over and from Sets Represented by Number Decision Diagrams.- Tree Automata and XPath on Compressed Trees.- Deeper Connections Between LTL and Alternating Automata.- The Structure of Subword Graphs and Suffix Trees of Fibonacci Words.- Observations on Determinization of Büchi Automata.- The Interval Rank of Monotonic Automata.- Compressing XML Documents Using Recursive Finite State Automata.- Non-backtracking Top-Down Algorithm for Checking Tree Automata Containment.- Size Reduction of Multitape Automata.- Robust Spelling Correction.- On Two-Dimensional Pattern Matching by Finite Automata.- Poster Abstracts.- Incremental andSemi-incremental Construction of Pseudo-Minimal Automata.- Is Learning RFSAs Better Than Learning DFAs?.- Learning Stochastic Finite Automata for Musical Style Recognition.- Simulation of Soliton Circuits.- Acyclic Automata with Easy-to-Find Short Regular Expressions.- On the Equivalence Problem for Programs with Mode Switching.- Automata and AB-Categorial Grammars.- On a Class of Bijective Binary Transducers with Finitary Description Despite Infinite State Set.

Erscheint lt. Verlag	14.2.2006
Reihe/Serie	Lecture Notes in Computer Science
Reihe/Serie	Theoretical Computer Science and General Issues
Zusatzinfo	XIII, 360 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	1170 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
Themenwelt	Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
Schlagworte	algorithm • Algorithm analysis and problem complexity • algorithms • Alphabet • automata implementations • Automata Theory • Cognition • Complexity theory • Finite Automata • Finite-State Systems • formal methods • Foundations • grammar systems • Linguistics • Logic • Music generation • Natural Language Processing • Pattern Matching • Regular Expressions • regular languages • Tree automata • XML processing
ISBN-10	3-540-31023-1 / 3540310231
ISBN-13	978-3-540-31023-5 / 9783540310235
Zustand	Neuware