000 06646nam a22006135i 4500
001 978-3-540-30500-2
003 DE-He213
005 20240730181913.0
007 cr nn 008mamaa
008 100715s2005 gw | s |||| 0|eng d
020 _a9783540305002
_9978-3-540-30500-2
024 7 _a10.1007/b105090
_2doi
050 4 _aQ334-342
050 4 _aTA347.A78
072 7 _aUYQ
_2bicssc
072 7 _aCOM004000
_2bisacsh
072 7 _aUYQ
_2thema
082 0 4 _a006.3
_223
245 1 0 _aImplementation and Application of Automata
_h[electronic resource] :
_b9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers /
_cedited by Michael Domaratzki, Alexander Okhotin, Kai Salomaa, Sheng Yu.
250 _a1st ed. 2005.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2005.
300 _aXII, 336 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3317
505 0 _aInvited Papers -- Automata-Theoretic Techniques for Analyzing Infinite-State Systems -- Enumerating Regular Expressions and Their Languages -- Contributed Papers -- A General Weighted Grammar Library -- On the Complexity of Hopcroft's State Minimization Algorithm -- Implementation of Catalytic P Systems -- Code Selection by Tree Series Transducers -- Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages -- Brute Force Determinization of NFAs by Means of State Covers -- Computing the Follow Automaton of an Expression -- Viral Gene Compression: Complexity and Verification -- Concatenation State Machines and Simple Functions -- FIRE Station: An Environment for Manipulating Finite Automata and Regular Expression Views -- Finding Finite Automata That Certify Termination of String Rewriting -- Linear Encoding Scheme for Weighted Finite Automata -- The Generalization of Generalized Automata: Expression Automata -- An Automata Approach to Match Gapped Sequence Tags Against Protein Database -- State Complexity of Concatenation and Complementation of Regular Languages -- Minimal Unambiguous ?NFA -- Substitutions, Trajectories and Noisy Channels -- State Complexity and the Monoid of Transformations of a Finite Set -- An Application of Quantum Finite Automata to Interactive Proof Systems (Extended Abstract) -- Time and Space Efficient Algorithms for Constrained Sequence Alignment -- Stochastic Context-Free Graph Grammars for Glycoprotein Modelling -- Parametric Weighted Finite Automata for Figure Drawing -- Regional Finite-State Error Repair -- Approximating Dependency Grammars Through Intersection of Regular Languages -- On the Equivalence-Checking Problem for a Model of Programs Related With Multi-tape Automata -- Poster Papers -- Tight Bounds for NFA to DFCATransformations for Binary Alphabets -- Simulating the Process of Gene Assembly in Ciliates -- A BDD-Like Implementation of an Automata Package -- Approximation to the Smallest Regular Expression for a Given Regular Language -- Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn-Rhodes Theory -- Does Hausdorff Dimension Measure Texture Complexity? -- Combining Regular Expressions with (Near-)Optimal Brzozowski Automata -- From Automata to Semilinear Sets: A Logical Solution for Sets ( , ) -- Myhill-Nerode Theorem for Sequential Transducers over Unique GCD-Monoids -- Minimalizations of NFA Using the Universal Automaton -- Two-Dimensional Pattern Matching by Two-Dimensional Online Tessellation Automata -- Size Reduction of Multitape Automata -- Testability of Oracle Automata -- Magic Numbers for Symmetric Difference NFAs.
520 _aThis 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.
650 0 _aArtificial intelligence.
_93407
650 0 _aComputer science.
_99832
650 0 _aMachine theory.
_9126542
650 0 _aAlgorithms.
_93390
650 1 4 _aArtificial Intelligence.
_93407
650 2 4 _aTheory of Computation.
_9126543
650 2 4 _aFormal Languages and Automata Theory.
_9126544
650 2 4 _aAlgorithms.
_93390
700 1 _aDomaratzki, Michael.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9126545
700 1 _aOkhotin, Alexander.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9126546
700 1 _aSalomaa, Kai.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9126547
700 1 _aYu, Sheng.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9126548
710 2 _aSpringerLink (Online service)
_9126549
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540243182
776 0 8 _iPrinted edition:
_z9783540806820
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3317
_9126550
856 4 0 _uhttps://doi.org/10.1007/b105090
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c91128
_d91128