Skip to main content
SpringerLink
Log in

Developments in Language Theory

18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings

  • Conference proceedings
  • © 2014

Overview

Editors:
  1. Arseny M. Shur

    1. Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg, Russia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Mikhail V. Volkov

    1. Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg, Russia

    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 8633)

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

Included in the following conference series:

Conference proceedings info: DLT 2014.

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 (30 papers)

  1. Front Matter

    Download chapter PDF

  2. Finite Automata and Regular Languages

    1. On Automatic Transitive Graphs

      • Dmitry Berdinsky, Bakhadyr Khoussainov
      Pages 1-12

    2. Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals

      • Janusz Brzozowski, Marek Szykuła
      Pages 13-24

    3. On the Average Complexity of Brzozowski’s Algorithm for Deterministic Automata with a Small Number of Final States

      • Sven De Felice, Cyril Nicaud
      Pages 25-36

    4. State Complexity of Deletion

      • Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
      Pages 37-48

    5. Semisimple Synchronizing Automata and the Wedderburn-Artin Theory

      • Jorge Almeida, Emanuele Rodaro
      Pages 49-60

    6. On Two Algorithmic Problems about Synchronizing Automata

      • Mikhail V. Berlinkov
      Pages 61-67

    7. Synchronizing Automata with Random Inputs

      • Vladimir V. Gusev
      Pages 68-75

    8. Graph Spectral Properties of Deterministic Finite Automata

      • Ryoma Sin’ya
      Pages 76-83

  3. Pushdown Automata and Related Models

    1. Input-Driven Pushdown Automata with Limited Nondeterminism

      • Alexander Okhotin, Kai Salomaa
      Pages 84-102

    2. How to Remove the Look-Ahead of Top-Down Tree Transducers

      • Joost Engelfriet, Sebastian Maneth, Helmut Seidl
      Pages 103-115

    3. Scope-Bounded Pushdown Languages

      • Salvatore La Torre, Margherita Napoli, Gennaro Parlato
      Pages 116-128

    4. Visibly Pushdown Transducers with Well-Nested Outputs

      • Pierre-Alain Reynier, Jean-Marc Talbot
      Pages 129-141

    5. Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing

      • Markus L. Schmid
      Pages 142-153

    6. Pumping Lemma and Ogden Lemma for Displacement Context-Free Grammars

      • Alexey Sorokin
      Pages 154-165

  4. Combinatorics and Algorithmics on Words

    1. Aperiodic Tilings and Entropy

      • Bruno Durand, Guilhem Gamard, Anaël Grandjean
      Pages 166-177

    2. k-Abelian Pattern Matching

      • Thorsten Ehlers, Florin Manea, Robert Mercaş, Dirk Nowotka
      Pages 178-190

    3. On k-Abelian Palindromic Rich and Poor Words

      • Juhani Karhumäki, Svetlana Puzynina
      Pages 191-202

    4. Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence

      • Juhani Karhumäki, Aleksi Saarela, Luca Q. Zamboni
      Pages 203-214

    5. Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word

      • Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń
      Pages 215-226
Back to top

Other volumes

  1. Developments in Language Theory

Keywords

About this book

This book constitutes the proceedings of the 18th International Conference on Developments in Language Theory, DLT 2014, held in Ekaterinburg, Russia, in August 2014. The 22 full papers and 5 short papers presented together with 3 invited talks were carefully reviewed and selected from 38 submissions. The papers are organized in topical subjects on 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 and Quantum Computing.

Editors and Affiliations

  • Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg, Russia

    Arseny M. Shur, Mikhail V. Volkov

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation