LEADER 08065nam 22008655 450 001 9910484987803321 005 20250702161751.0 010 $a1-280-38660-6 010 $a9786613564528 010 $a3-642-13089-5 024 7 $a10.1007/978-3-642-13089-2 035 $a(CKB)2550000000011542 035 $a(SSID)ssj0000399489 035 $a(PQKBManifestationID)11297911 035 $a(PQKBTitleCode)TC0000399489 035 $a(PQKBWorkID)10376500 035 $a(PQKB)11026583 035 $a(DE-He213)978-3-642-13089-2 035 $a(MiAaPQ)EBC3065260 035 $a(PPN)14907302X 035 $a(BIP)30400754 035 $a(EXLCZ)992550000000011542 100 $a20100509d2010 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aLanguage and Automata Theory and Applications $e4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings /$fedited by Carlos Martin-Vide, Henning Fernau, Adrian Horia Dediu 205 $a1st ed. 2010. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2010. 215 $a1 online resource (XIV, 622 p. 92 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v6031 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-642-13088-7 320 $aIncludes bibliographical references and index. 327 $aInvited Talks -- Complexity in Convex Languages -- Three Learnable Models for the Description of Language -- Arbology: Trees and Pushdown Automata -- Analysis of Communicating Automata -- Regular Papers -- Complexity of the Satisfiability Problem for a Class of Propositional Schemata -- A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton -- A Fast Longest Common Subsequence Algorithm for Similar Strings -- Abelian Square-Free Partial Words -- Avoidable Binary Patterns in Partial Words -- Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata -- Pregroup Grammars with Letter Promotions -- A Hierarchical Classification of First-Order Recurrent Neural Networks -- Choosing Word Occurrences for the Smallest Grammar Problem -- Agreement and Cliticization in Italian: A Pregroup Analysis -- Geometricity of Binary Regular Languages -- On the Expressive Power of FO[?+?] -- Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach -- Operator Precedence and the Visibly Pushdown Property -- On the Maximal Number of Cubic Runs in a String -- On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT -- Parametric Metric Interval Temporal Logic -- Short Witnesses and Accepting Lassos in ?-Automata -- Grammar-Based Compression in a Streaming Model -- Simplifying Regular Expressions -- A Programming Language Tailored to the Specification and Solution of Differential Equations Describing Processes on Networks -- The Inclusion Problem for Regular Expressions -- Learnability of Automatic Classes -- Untestable Properties Expressible with Four First-Order Quantifiers -- The Copying Power of Well-Nested Multiple Context-Free Grammars -- Post Correspondence Problem with Partially Commutative Alphabets -- Reversible Pushdown Automata -- StringExtension Learning Using Lattices -- The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape -- Primitive Words Are Unavoidable for Context-Free Languages -- Modal Nonassociative Lambek Calculus with Assumptions: Complexity and Context-Freeness -- Hard Counting Problems for Partial Words -- Exact Analysis of Horspool?s and Sunday?s Pattern Matching Algorithms with Probabilistic Arithmetic Automata -- SA-REPC ? Sequence Alignment with Regular Expression Path Constraint -- CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages -- A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems -- Using Sums-of-Products for Non-standard Reasoning -- Restarting Automata with Structured Output and Functional Generative Description -- A Randomized Numerical Aligner (rNA) -- Language-Based Comparison of Petri Nets with Black Tokens, Pure Names and Ordered Data -- Verifying Complex Continuous Real-Time Systems with Coinductive CLP(R) -- Incremental Building in Peptide Computing to Solve Hamiltonian Path Problem -- Variable Automata over Infinite Alphabets -- Some Minimality Results on Biresidual and Biseparable Automata -- Extending Stochastic Context-Free Grammars for an Application in Bioinformatics -- Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages -- Complexity of Guided Insertion-Deletion in RNA-Editing. 330 $aThese proceedings containall the papers that werepresented at the 4th Inter- tional Conference on Language and Automata Theory and Applications (LATA 2010), held in Trier, Germany, during May 24-28, 2010. The scope of LATA is rather broad, including: algebraic language theory; algorithms on automata and words; automata and logic; automata for system analysis and program veri'cation; automata, concurrency and Petri nets; cel- lar automata; combinatorics on words; computability; computational compl- ity; computer linguistics; data and image compression; decidability questions on words and languages; descriptional complexity; DNA and other models of bio-inspired computing; document engineering; foundations of ?nite state te- nology; fuzzy and rough languages; grammars (Chomsky hierarchy, contextual, multidimensional, uni'cation, categorial, etc. ); grammars and automata arc- tectures; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; language-based cryptog- phy; language-theoretic foundations of arti'cial intelligence and arti'cial life; neuralnetworks;parallelandregulatedrewriting;parsing;patternmatching and pattern recognition; patterns and codes; power series; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; symbolic dynamics; term rewriting; text algorithms; textretrieval;transducers;trees,treelanguagesandtreemachines;andweighted machines. LATA 2010 received 115 submissions, many among them of good quality. Each one was reviewed by at least three Program Committee members plus, in mostcases,byadditionalexternalreferees. Afterathoroughandvividdiscussion phase, the committee decided to accept 47 papers (which means an acceptance rate of 40. 86%). The conference program also included four invited talks. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v6031 606 $aComputer programming 606 $aCompilers (Computer programs) 606 $aPattern recognition systems 606 $aComputer science 606 $aAlgorithms 606 $aArtificial intelligence 606 $aProgramming Techniques 606 $aCompilers and Interpreters 606 $aAutomated Pattern Recognition 606 $aTheory of Computation 606 $aAlgorithms 606 $aArtificial Intelligence 615 0$aComputer programming. 615 0$aCompilers (Computer programs) 615 0$aPattern recognition systems. 615 0$aComputer science. 615 0$aAlgorithms. 615 0$aArtificial intelligence. 615 14$aProgramming Techniques. 615 24$aCompilers and Interpreters. 615 24$aAutomated Pattern Recognition. 615 24$aTheory of Computation. 615 24$aAlgorithms. 615 24$aArtificial Intelligence. 676 $a410.1/15 701 $aHoria Dediu$b Adrian$01751606 701 $aFernau$b Henning$01731916 701 $aMartin Vide$b Carlos$0168387 712 12$aLATA 2010 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484987803321 996 $aLanguage and automata theory and applications$94186600 997 $aUNINA