Skip to main content
SpringerLink
Log in

Descriptional Complexity of Formal Systems

18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings

  • Conference proceedings
  • © 2016

Overview

Editors:
  1. Cezar Câmpeanu

    1. University of Prince Edward Island, Charlottetown, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Florin Manea

    1. Universität Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. 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

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

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

Included in the following conference series:

Conference proceedings info: DCFS 2016.

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

  1. Front Matter

    Pages I-XVI
    Download chapter PDF

  2. Completely Reachable Automata

    • Eugenija A. Bondar, Mikhail V. Volkov
    Pages 1-17

  3. Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

    • Gabriel Istrate, Cosmin Bonchiş
    Pages 18-28

  4. Self-Verifying Finite Automata and Descriptional Complexity

    • Galina Jirásková
    Pages 29-44

  5. On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

    • Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis
    Pages 45-59

  6. Unrestricted State Complexity of Binary Operations on Regular Languages

    • Janusz Brzozowski
    Pages 60-72

  7. On the State Complexity of the Shuffle of Regular Languages

    • Janusz Brzozowski, Galina Jirásková, Bo Liu, Aayush Rajasekaran, Marek Szykuła
    Pages 73-86

  8. MSO-definable Properties of Muller Context-Free Languages Are Decidable

    • Zoltán Ésik, Szabolcs Iván
    Pages 87-97

  9. Contextual Array Grammars with Matrix and Regular Control

    • Henning Fernau, Rudolf Freund, Rani Siromoney, K. G. Subramanian
    Pages 98-110

  10. Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

    • Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman
    Pages 111-125

  11. Operations on Weakly Recognizing Morphisms

    • Lukas Fleischer, Manfred Kufleitner
    Pages 126-137

  12. Descriptional Complexity of Bounded Regular Languages

    • Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt
    Pages 138-152

  13. The Complexity of Languages Resulting from the Concatenation Operation

    • Galina Jirásková, Alexander Szabari, Juraj Šebej
    Pages 153-167

  14. Minimal and Reduced Reversible Automata

    • Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
    Pages 168-179

  15. Unary Self-verifying Symmetric Difference Automata

    • Laurette Marais, Lynette van Zijl
    Pages 180-191

  16. State Complexity of Prefix Distance of Subregular Languages

    • Timothy Ng, David Rappaport, Kai Salomaa
    Pages 192-204

  17. Two Results on Discontinuous Input Processing

    • Vojtěch Vorel
    Pages 205-216

  18. Back Matter

    Pages 217-217
    Download chapter PDF
Back to top

Other volumes

  1. Descriptional Complexity of Formal Systems

Keywords

About this book

his book constitutes the refereed proceedings of the 18th International Conference on Descriptional Complexity of Formal Systems, DCFS 2016, held in Bucharest, Romania, in July 2016. The 13 full papers presented together with 4 invited talks were carefully reviewed and selected from 21 submissions.Descriptional Complexity is a field in Computer Science that deals with the size of all kind of objects that occur in computational models, such as Turing Machines, finte automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity. 

Editors and Affiliations

  • University of Prince Edward Island, Charlottetown, Canada

    Cezar Câmpeanu

  • Universität Kiel, Kiel, Germany

    Florin Manea

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

    Jeffrey Shallit

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation