Lecture Notes in Computer Science 4783 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Jan Holub Jan Žd’árek (Eds.) Implementation and Application of Automata 12th International Conference, CIAA 2007 Prague, Czech Republic, July 16-18, 2007 Revised Selected Papers 1 3 VolumeEditors JanHolub CzechTechnicalUniversityinPrague FacultyofElectricalEngineering DepartmentofComputerScienceandEngineering Karlovonámeˇstí13,Praha2,CZ–12135,CzechRepublic E-mail:[email protected] JanŽd’árek CzechTechnicalUniversityinPrague FacultyofElectricalEngineering DepartmentofComputerScienceandEngineering Karlovonámeˇstí13,Praha2,CZ–12135,CzechRepublic E-mail:[email protected] LibraryofCongressControlNumber:2007937688 CRSubjectClassification(1998):F.1.1-3,F.4.2-3,F.2 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-76335-XSpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-76335-2SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2007 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12182312 06/3180 543210 Preface The 12th International Conference on Implementation and Application of Au- tomataCIAA2007washeldattheCzechTechnicalUniversityinPrague,Czech Republic on July 16–18,2007. These proceedings contain the papers that were presented at CIAA 2007, as well as the abstracts of the poster papers that were displayed during the conference. The proceedings also include the abstracts and extended abstracts offourinvitedlecturespresentedbyGheorghePa˘un,MichaelRiley,MosheVardi, and Bruce W. Watson. The 23 regular papers and 7 poster papers were selected from 79 submitted paperscoveringvarioustopics in the theory,implementation,andapplicationof automataandrelatedstructures.Eachsubmittedpaperwasreviewedbyatleast threeProgramCommitteemembers,withtheassistanceofreferees.Theauthors of the papers presented here come from the following countries: Canada, Czech Republic, Denmark, Finland, France, Germany, Greece, Israel, Italy, Poland, Romania, Russia, South Africa, Spain, Sweden, UK, and USA. We wish to thank all those who made this meeting possible: the authors for submitting papers, the Program Committee members and external referees (listed on pages VII and VIII) for their excellent work, and last but not least ourfourinvitedspeakers.Finally,wewishtoexpressoursincereappreciationto the sponsors and local organizers. July 2007 Jan Holub Jan Zˇd’´arek Organization Program Committee Marie-Pierre B´eal Universit´e de Marne-la-Vall´ee,France Cristian S. Calude University of Auckland, New Zealand Jean-Marc Champarnaud Universit´e de Rouen, France Erzs´ebet Csuhaj-Varju´ Hungarian Academy of Sciences, Hungary Ju¨rgen Dassow University of Magdeburg, Germany Jacques Farr´e ESSI, France Jozef Gruska Masaryk University, Czech Republic Tero Harju University of Turku, Finland Jan Holub, Co-chair Czech Technical University in Prague, Czech Republic Markus Holzer Technische Universit¨at Mu¨nchen, Germany Juraj Hromkoviˇc ETH Zurich, Switzerland Oscar H. Ibarra University of California, Santa Barbara,USA Masami Ito Kyoto Sangyo University, Japan Kazuo Iwama Kyoto University, Japan Juhani Karhuma¨ki University of Turku, Finland Werner Kuich Vienna University of Technology, Austria Denis Maurel Universit´e Franc¸ois-Rabelais de Tours, France Giancarlo Mauri Universita` degli Studi di Milano–Bicocca, Italy BoˇrivojMelichar, Co-chair Czech Technical University in Prague, Czech Republic Mehryar Mohri New York University, USA Gheorghe Pa˘un Romanian Academy, Romania Giovanni Pighizzini Universita` degli Studi di Milano, Italy Jean-E´ric Pin LIAFA, France Bala Ravikumar Sonoma State University, USA Wojciech Rytter Warsaw University, Poland Kai Salomaa Queen’s University, Canada Pierluigi San Pietro Politecnico di Milano, Italy Bow-Yaw Wang Academia Sinica, Taiwan Bruce Watson University of Pretoria, South Africa; Sagantec, USA Hsu-Chun Yen National Taiwan University, Taiwan Sheng Yu University of Western Ontario, Canada VIII Organization Steering Committee Jean-Marc Champarnaud Universit´e de Rouen, France Oscar H. Ibarra University of California, Santa Barbara,USA Denis Maurel Universit´e Franc¸ois-Rabelais de Tours, France Derick Wood Hong Kong University of Science and Technology, Hong Kong Sheng Yu, Chair University of Western Ontario, Canada External Referees Cyril Allauzen Paul Gastin Cyril Nicaud Bruno Apolloni Cagdas Gerede Hidenosuke Nishio B´eatrice Bouchou Massimiliano Goldwurm Alexander Okhotin Sakthi Balan Hermann Gruber Beatrice Palano Miroslav Bal´ık Franck Guingne Andrei Paun Pawel Baturo Vesa Halava Klaus Reinhardt Franziska Biegler Mika Hirvensalo Dominique Revuz Paola Bonizzoni Florian Horn Jacques Sakarovitch Daniel Brown Pao-Ann Hsiung Nicolae Santean Gregory Budzban Lucian Ilie Sylvain Schmitz Elena Calude Costas Iliopoulos Sebastian Seibert PascalCaron Christos Kapoutsis Patrick Sol´e Christian Choffrut Ernest Ketcha Ngassam Paola Spoletini Loek Cleophas Derrick Kourie Lynn Stauffer Julien Cl´ement Gregory Kucherov Ralf Stiebe Jean-Michel Couvreur Martin Kutrib Tinus Strauss Eugen Czeizler Slawomir Lasota Sophie Tison Zhe Dang Alberto Leporati Nicholas Tran Gianluca Della Vedova Martin Leucker Kumar Neeraj Verma Michael Domaratzki Andreas Malcher Halava Vesa Claudio Ferretti Carlo Mereghetti Farn Wang Markus Forsberg Manal Mohamed Claudio Zandron Dominik Freydenberger Mark-Jan Nederhof Anna Frid Florent Nicart Organizing Committee Miroslav Bal´ık, Co-chair Jan Holub, Co-chair Ladislav Vagner Michal Vora´ˇcek Jan Zˇd’´arek URL: http://www.stringology.org/ Organization IX Conference Sponsors Czech Technical University in Prague IBM Czech Republic Sun Microsystems Czech Table of Contents I Invited Talks Spiking Neural P Systems Used as Acceptors and Transducers......... 1 Gheorghe P˘aun Linear-Time Model Checking: Automata Theory in Practice........... 5 Moshe Y. Vardi OpenFst: A General and Efficient Weighted Finite-State Transducer Library ......................................................... 11 Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, and Mehryar Mohri Automata Applications in Chip-Design Software ..................... 24 Bruce W. Watson II Contributed Talks Synchronizing Automata Preserving a Chain of Partial Orders......... 27 Mikhail V. Volkov Reducing Acyclic Cover Transducers ............................... 38 Jean-Marc Champarnaud, Franck Guingne, and Jacques Farr´e On-the-Fly Stuttering in the Construction of Deterministic ω-Automata..................................................... 51 Joachim Klein and Christel Baier Average Value and Variance of Pattern Statistics in Rational Models ... 62 Massimiliano Goldwurm and Roberto Radicioni Weighted Automata and Weighted Logics with Discounting ........... 73 Manfred Droste and George Rahonis Regulated Nondeterminism in Pushdown Automata .................. 85 Martin Kutrib, Andreas Malcher, and Larissa Werlein Deterministic Caterpillar Expressions............................... 97 Kai Salomaa, Sheng Yu, and Jinfeng Zan Backwardand ForwardBisimulation Minimisation of Tree Automata ... 109 Johanna H¨ogberg, Andreas Maletti, and Jonathan May XII Table of Contents An Implementation of Deterministic Tree Automata Minimization ..... 122 Rafael C. Carrasco, Jan Daciuk, and Mikel L. Forcada Accelerating Boyer Moore Searches on Binary Texts.................. 130 Shmuel T. Klein and Miri Kopel Ben-Nissan On the Suffix Automaton with Mismatches.......................... 144 Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, and Filippo Mignosi On String Matching in Chunked Texts.............................. 157 Hannu Peltola and Jorma Tarhio Factor Automata of Automata and Applications ..................... 168 Mehryar Mohri, Pedro Moreno, and Eugene Weinstein Subset Seed Automaton .......................................... 180 Gregory Kucherov, Laurent No´e, and Mikhail Roytberg A Measure for the Degree of Nondeterminism of Context-Free Languages ...................................................... 192 Frantiˇsek Mra´z, Martin Pla´tek, and Friedrich Otto Efficient Computation of Throughput Values of Context-Free Languages ...................................................... 203 Didier Caucal, Jurek Czyzowicz, Wojciech Fraczak, and Wojciech Rytter Analyzing Ambiguity of Context-Free Grammars..................... 214 Claus Brabrand, Robert Giegerich, and Anders Møller Efficient Enumeration of Regular Languages......................... 226 Margareta Ackerman and Jeffrey Shallit Multi-grain Relations............................................. 243 Franc¸ois Barth´elemy Memory Reduction for Strategies in Infinite Games................... 253 Michael Holtmann and Christof Lo¨ding Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms .................................................... 265 Magnus Steinby and Ca˘t˘alin Ionu¸t Tˆırna˘uca˘ Finite State Automata Representing Two-Dimensional Subshifts ....... 277 Nataˇsa Jonoska and Joni B. Pirnot Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages ...................................... 290 Marcella Anselmo, Dora Giammarresi, and Maria Madonia Table of Contents XIII III Poster Abstracts REGAL: A Library to Randomly and Exhaustively Generate Automata....................................................... 303 Fr´ed´erique Bassino, Julien David, and Cyril Nicaud A Finite-State Super-Chunker ..................................... 306 Olivier Blanc, Matthieu Constant, and Patrick Watrin The Constrained Longest Common Subsequence Problem for Degenerate Strings ............................................... 309 Costas Iliopoulos, M. Sohel Rahman, Michal Vora´ˇcek, and Ladislav Vagner Finite Automata Accepting Star-Connected Languages ............... 312 Barbara Klunder Efficiently Matching with Local Grammars Using Prefix Overlay Transducers ..................................................... 314 Clemens Marschner Significant Subpatterns Matching .................................. 317 Jan Sˇupol A New Method for Compiling ParallelReplacement Rules............. 320 Anssi Yli-Jyra¨ and Kimmo Koskenniemi Author Index.................................................. 323