Implementation and Application of Automata: 9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected PapersMichael Domaratzki Springer Science & Business Media, 31 ene 2005 - 336 páginas This volume of Lecture Notes in Computer Science contains the revised versions of the papers presented at the 9th International Conference on Implemen- tion and Application of Automata, CIAA 2004. Also included are the extended abstracts of the posters accepted to the conference. The conference was held at Queen’s University in Kingston, Ontario, Canada on July 22–24, 2004. As for its predecessors, the theme of CIAA 2004 was the implementation of automata and grammars of all types and their application in other ?elds. The topics of the papers presented at the conference range from applications of automata in natural language and speech processing to protein sequencingandgenecompression,andfromstatecomplexityandnewalgorithms for automata operations to applications of quantum ?nite automata. The25regularpapersand14posterpaperswereselectedfrom62submissions totheconference.EachsubmittedpaperwasevaluatedbyatleastthreeProgram Committee members, with the help of external referees. Based on the referee reports, the paper “Substitutions, Trajectories and Noisy Channels” by L. Kari, S. Konstantinidis and P. Sos ́ ?k was chosen as the winner of the CIAA 2004 Best Paper Award. The award is sponsored by the University of California at Santa Barbara. The authors of the papers presented here come from the following countries and regions: Austria, Canada, Czech Republic, Finland, France, Germany, Hong Kong, Netherlands, Portugal, Russia, Slovakia, South Africa, Spain, UK, and USA. |
Índice
Invited Papers | 1 |
Contributed Papers | 23 |
Implementation of Catalytic P Systems | 45 |
Some Nonsemidecidability Problems for Linear and Deterministic | 68 |
Computing the Follow Automaton of an Expression | 90 |
Concatenation State Machines and Simple Functions | 113 |
Finding Finite Automata That Certify Termination of String Rewriting | 134 |
Expression Automata | 156 |
Substitutions Trajectories and Noisy Channels | 202 |
An Application of Quantum Finite Automata to Interactive Proof | 225 |
Stochastic ContextFree Graph Grammars for Glycoprotein Modelling | 247 |
Regional FiniteState Error Repair | 269 |
Approximating Dependency Grammars Through Intersection | 281 |
Poster Papers | 306 |
Combining Regular Expressions with NearOptimal Brzozowski | 319 |
TwoDimensional Pattern Matching by TwoDimensional Online | 327 |
Otras ediciones - Ver todo
Implementation and Application of Automata: 9th International Conference ... Michael Domaratzki,Alexander Okhotin,Kai Salomaa,Sheng Yu Vista previa restringida - 2005 |
Implementation and Application of Automata: 9th International Conference ... Michael Domaratzki,Alexander Okhotin,Kai Salomaa,Sheng Yu Vista previa restringida - 2004 |
Implementation and Application of Automata: 9th International Conference ... Michael Domaratzki,Alexander Okhotin,Kai Salomaa,Sheng Yu No hay ninguna vista previa disponible - 2004 |
Términos y frases comunes
accepting algorithm alignment alphabet applications approach assume automata automaton bound called closed complexity Computer Computer Science concatenation consider construction contains context context-free languages corresponding cover decidable defined definition denote dependency derivatives describe deterministic determinization different elements equivalent error example exists final finite finite automata first formal function give given grammar graph Hence holds implementation initial input introduced labelled least Lemma length linear machine mass matching minimal node Note obtained operation output pair parse path pattern position present problem productions programs Proof properties Proposition prove recognizing References regular expression regular languages relation representation represented respectively result rules running satisfies sequence simple space step string structure subset symbol techniques termination Theorem Theory transformations transitions tree University verifier weighted