Skip to main content
SpringerLink
Log in
Book cover

Descriptional Complexity of Formal Systems

17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings

  • Conference proceedings
  • © 2015

Overview

Editors:
  1. Jeffrey Shallit

    1. School of Computer Science, University of Waterloo, Waterloo, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Alexander Okhotin

    1. Department of Mathematics, University of Turku, Turku, Finland

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

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

Included in the following conference series:

Conference proceedings info: DCFS 2015.

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 EPUB and 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 (24 papers)

  1. Front Matter

    Pages I-XII
    Download chapter PDF

  2. Invited Talk

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Unambiguity in Automata Theory

      • Thomas Colcombet
      Pages 3-18

  3. Contributed Papers

    1. Front Matter

      Pages 19-19
      Download chapter PDF

    2. Partial Derivative Automaton for Regular Expressions with Shuffle

      • Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis
      Pages 21-32

    3. Upper Bound on Syntactic Complexity of Suffix-Free Languages

      • Janusz Brzozowski, Marek Szykuła
      Pages 33-45

    4. Nondeterministic Tree Width of Regular Languages

      • Cezar Câmpeanu, Kai Salomaa
      Pages 46-57

    5. Integer Complexity: Experimental and Analytical Results II

      • Juris Čerņenoks, Jānis Iraids, Mārtiņš Opmanis, Rihards Opmanis, Kārlis Podnieks
      Pages 58-69

    6. Square on Ideal, Closed and Free Languages

      • Kristína Čevorová
      Pages 70-80

    7. A Tentative Approach for the Wadge-Wagner Hierarchy of Regular Tree Languages of Index [0, 2]

      • Jacques Duparc, Kevin Fournier
      Pages 81-92

    8. Compressibility of Finite Languages by Grammars

      • Sebastian Eberhard, Stefan Hetzl
      Pages 93-104

    9. On the Complexity and Decidability of Some Problems Involving Shuffle

      • Joey Eremondi, Oscar H. Ibarra, Ian McQuillan
      Pages 105-116

    10. On the Computational Complexity of Problems Related to Distinguishability Sets

      • Markus Holzer, Sebastian Jakobi
      Pages 117-128

    11. Prefix-Free Subsets of Regular Languages and Descriptional Complexity

      • Jozef Štefan Jirásek, Juraj Šebej
      Pages 129-140

    12. Transducer Descriptions of DNA Code Properties and Undecidability of Antimorphic Problems

      • Lila Kari, Stavros Konstantinidis, Steffen Kopecki
      Pages 141-152

    13. On Simulation Cost of Unary Limited Automata

      • Martin Kutrib, Matthias Wendlandt
      Pages 153-164

    14. On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata

      • Kent Kwee, Friedrich Otto
      Pages 165-176

    15. Quantum Queries on Permutations

      • Taisia Mischenko-Slatenkova, Alina Vasilieva, Ilja Kucevalovs, Rūsiņš Freivalds
      Pages 177-184

    16. Complement on Free and Ideal Languages

      • Peter Mlynárčik
      Pages 185-196

    17. Universal Disjunctive Concatenation and Star

      • Nelma Moreira, Giovanni Pighizzini, Rogério Reis
      Pages 197-208
Back to top

Other volumes

  1. Descriptional Complexity of Formal Systems

Keywords

About this book

This book constitutes the refereed proceedings of the 17th International Conference on Descriptional Complexity of Formal Systems, DCFS 2015, held in Waterloo, ON, Canada, in June 2015. The 23 full papers presented together with 2 invited talks were carefully reviewed and selected from 29 submissions. The subject of the workshop was descriptional complexity. Roughly speaking, this field is concerned with the size of objects in various mathematical models of computation, such as finite automata, pushdown automata, and Turing machines. Descriptional complexity serves as a theoretical representation of physical realizations, such as the engineering complexity of computer software and hardware. It also models similar complexity phenomena in other areas of computer science, including unconventional computing and bioinformatics.

Editors and Affiliations

  • School of Computer Science, University of Waterloo, Waterloo, Canada

    Jeffrey Shallit

  • Department of Mathematics, University of Turku, Turku, Finland

    Alexander Okhotin

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation