| Description |
1 online resource (xiv, 478 pages) : illustrations |
| Series |
Lecture notes in computer science, 1611-3349 ; 7410 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 7410. 1611-3349
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
The Kind Hearted Dragon Prof. Sheng Yu, 1950-2012 / Andrew L. Szilard -- P and dP Automata: Unconventional versus Classical Automata / Erzsébet Csuhaj-Varjú -- Recovering Strings in Oracles: Quantum and Classic / Kazuo Iwama -- Determinism vs. Nondeterminism for Two-Way Automata: Representing the Meaning of States by Logical Formulæ / Juraj Hromkovič, Rastislav Královič, Richard Královič and Richard Štefanec -- Cellular Automata, the Collatz Conjecture and Powers of 3/2 / Jarkko Kari -- Quotient Complexities of Atoms of Regular Languages / Janusz Brzozowski and Hellis Tamm -- Decidability of Geometricity of Regular Languages / Marie-Pierre Béal, Jean-Marc Champarnaud, Jean-Philippe Dubernard, Hadrien Jeanne and Sylvain Lombardy -- Inside the Class of REGEX Languages / Markus L. Schmid -- Computing the Edit-Distance between a Regular Language and a Context-Free Language / Yo-Sub Han, Sang-Ki Ko and Kai Salomaa -- Semigroups with a Context-Free Word Problem / Michael Hoffmann, Derek F. Holt, Matthew D. Owens and Richard M. Thomas -- Generalized Derivations with Synchronized Context-Free Grammars / Markus Holzer, Sebastian Jakobi and Ian McQuillan -- Non-erasing Variants of the Chomsky-Schützenberger Theorem / Alexander Okhotin -- Regular and Context-Free Pattern Languages over Small Alphabets / Daniel Reidenbach and Markus L. Schmid |
|
On Context-Free Languages of Scattered Words / Zoltan Ésik and Satoshi Okawa -- Homomorphisms Preserving Deterministic Context-Free Languages / Tommi Lehtinen and Alexander Okhotin -- Unary Coded NP-Complete Languages in ASPACE (log log n) / Viliam Geffert and Dana Pardubská -- Dense Completeness / Andreas Krebs and Klaus-Jörn Lange -- From Equivalence to Almost-Equivalence, and Beyond--Minimizing Automata with Errors (Extended Abstract) / Markus Holzer and Sebastian Jakobi -- Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata / Christos A. Kapoutsis and Nans Lefebvre -- States and Heads Do Count for Unary Multi-head Finite Automata / Martin Kutrib, Andreas Malcher and Matthias Wendlandt -- Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness / Mathieu Caralp, Pierre-Alain Reynier and Jean-Marc Talbot -- Unambiguous Constrained Automata / Michaël Cadilhac, Alain Finkel and Pierre McKenzie -- Two-Dimensional Sgraffito Automata / Daniel Průša and František Mráz -- Two-Way Transducers with a Two-Way Output Tape / Olivier Carton -- Learning Rational Functions / Adrien Boiret, Aurélien Lemay and Joachim Niehren -- Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata / Giovanna J. Lavado, Giovanni Pighizzini and Shinnosuke Seki -- Fine and Wilf's Theorem for k-Abelian Periods / Juhani Karhumäki, Svetlana Puzynina and Aleksi Saarela -- Pseudoperiodic Words / Alexandre Blondin Massé, Sébastien Gaboury and Sylvain Hallé |
|
Acceptance Conditions for [omega]-Languages / Alberto Dennunzio, Enrico Formenti and Julien Provillard -- Checking Determinism of Regular Expressions with Counting / Haiming Chen and Ping Lu -- Biautomata for k-Piecewise Testable Languages / Ondřej Klíma and Libor Polák -- On Centralized PC Grammar Systems with Context-Sensitive Components / Friedrich Otto -- Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars / Matthias Büchse, Andreas Maletti and Heiko Vogler -- The State Complexity of Star-Complement-Star / Galina Jirásková and Jeffrey Shallit -- On State Complexity of Finite Word and Tree Languages / Aniruddh Gandhi, Bakhadyr Khoussainov and Jiamou Liu -- Squares in Binary Partial Words / Francine Blanchet-Sadri, Yang Jiao and John M. Machacek -- The Avoidability of Cubes under Permutations / Florin Manea, Mike Müller and Dirk Nowotka -- Hairpin Completion with Bounded Stem-Loop / Szilárd Zsolt Fazekas, Robert Mercaş and Kayoko Shikishima-Tsuji -- Morphic Primitivity and Alphabet Reductions / Hossein Nevisi and Daniel Reidenbach -- On a Hierarchy of Languages with Catenation and Shuffle / Nils Erik Flick and Manfred Kudlek -- Characterizing Languages by Normalization and Termination in String Rewriting (Extended Abstract) / Jeroen Ketema and Jakob Grue Simonsen -- Geometry and Dynamics of the Besicovitch and Weyl Spaces / Ville Salo and Ilkka Törmä -- A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay / Laura Giambruno, Sabrina Mantaci, Jean Néraud and Carla Selmi |
| Summary |
Annotation This book constitutes the refereed proceedings of the 16th International Conference on Developments in Language Theory, DLT 2012, held in Taipei, Taiwan, in August 2012. The 34 regular papers presented were carefully reviewed and selected from numerous submissions. The volume also contains the papers or extended abstracts of 4 invited lectures, as well as a special memorial presentation in honor of Sheng Yu. The topics covered include grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; algorithmic, combinatorial and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular automata; polyominoes and multidimensional patterns; decidability questions; image manipulation and compression; efficient text algorithms; relationships to cryptography, concurrency, complexity theory and logic; bio-inspired computing; quantum computing |
| Analysis |
Computer science |
|
Coding theory |
|
Logic design |
|
Computational complexity |
|
Computation by Abstract Devices |
|
Mathematical Logic and Formal Languages |
|
Logics and Meanings of Programs |
|
Coding and Information Theory |
|
Discrete Mathematics in Computer Science |
|
computerwetenschappen |
|
computer sciences |
|
wiskunde |
|
mathematics |
|
informatietheorie |
|
information theory |
|
logica |
|
logic |
|
computational science |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
| Notes |
International conference proceedings |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Online resource; title from PDF title page (SpringerLink, viewed August 10, 2012) |
| In |
Springer eBooks |
| Subject |
Formal languages -- Congresses
|
|
Informatique.
|
|
Formal languages
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Yen, Hsu-Chun, 1958-
|
|
Ibarra, Oscar H.
|
| ISBN |
9783642316531 |
|
3642316530 |
|
3642316522 |
|
9783642316524 |
|
