Skip to main content
SpringerLink
Log in

Developments in Language Theory

12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008, Proceedings

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Masami Ito
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Masafumi Toyama
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5257)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: DLT 2008.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (42 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Talks

    1. Iteration Semirings

      • Zoltán Ésik
      Pages 1-20

    2. Various Aspects of Finite Quantum Automata

      • Mika Hirvensalo
      Pages 21-33

    3. On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes

      • Juraj Hromkovič, Georg Schnitger
      Pages 34-55

    4. Selected Ideas Used for Decidability and Undecidability of Bisimilarity

      • Petr Jančar
      Pages 56-71

    5. The Frobenius Problem and Its Generalizations

      • Jeffrey Shallit
      Pages 72-83

    6. Well Quasi-orders in Formal Language Theory

      • Flavio D’Alessandro, Stefano Varricchio
      Pages 84-95

  3. Contributed Papers

    1. On the Non-deterministic Communication Complexity of Regular Languages

      • Anil Ada
      Pages 96-107

    2. General Algorithms for Testing the Ambiguity of Finite Automata

      • Cyril Allauzen, Mehryar Mohri, Ashish Rastogi
      Pages 108-120

    3. Emptiness of Multi-pushdown Automata Is 2ETIME-Complete

      • Mohamed Faouzi Atig, Benedikt Bollig, Peter Habermehl
      Pages 121-133

    4. The Average State Complexity of the Star of a Finite Set of Words Is Linear

      • Frédérique Bassino, Laura Giambruno, Cyril Nicaud
      Pages 134-145

    5. On the Computational Capacity of Parallel Communicating Finite Automata

      • Henning Bordihn, Martin Kutrib, Andreas Malcher
      Pages 146-157

    6. On a Generalization of Standard Episturmian Morphisms

      • Michelangelo Bucci, Aldo de Luca, Alessandro De Luca
      Pages 158-169

    7. Universal Recursively Enumerable Sets of Strings

      • Cristian S. Calude, André Nies, Ludwig Staiger, Frank Stephan
      Pages 170-182

    8. Algorithmically Independent Sequences

      • Cristian S. Calude, Marius Zimand
      Pages 183-195

    9. Relationally Periodic Sequences and Subword Complexity

      • Julien Cassaigne, Tomi Kärki, Luca Q. Zamboni
      Pages 196-205

    10. Bounds on Powers in Strings

      • Maxime Crochemore, Szilárd Zsolt Fazekas, Costas Iliopoulos, Inuka Jayasekera
      Pages 206-215

    11. When Is Reachability Intrinsically Decidable?

      • Barbara F. Csima, Bakhadyr Khoussainov
      Pages 216-227

    12. Some New Modes of Competence-Based Derivations in CD Grammar Systems

      • Erzsébet Csuhaj-Varjú, Jürgen Dassow, György Vaszil
      Pages 228-239

    13. The Synchronization Problem for Strongly Transitive Automata

      • Arturo Carpi, Flavio D’Alessandro
      Pages 240-251
Back to top

Other volumes

  1. Developments in Language Theory

Keywords

About this book

This book constitutes the refereed proceedings of the 12th International Conference on Developments in Language Theory, DLT 2008, held in Kyoto, Japan, September 2008. The 36 revised full papers presented together with 6 invited papers were carefully reviewed and selected from 102 submissions. All important issues in language theory are addressed including 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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation