Skip to main content
SpringerLink
Log in
Book cover

Descriptional Complexity of Formal Systems

20th IFIP WG 1.02 International Conference, DCFS 2018, Halifax, NS, Canada, July 25–27, 2018, Proceedings

  • Conference proceedings
  • © 2018

Overview

Editors:
  1. Stavros Konstantinidis

    1. Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Giovanni Pighizzini

    1. Dipartimento di Informatica e Comunicazi, Universita degli Studi di Milano, Milan, Italy

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

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

Included in the following conference series:

Conference proceedings info: DCFS 2018.

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

  1. Front Matter

    Pages I-XIV
    Download chapter PDF

  2. Finite Automata and Randomness

    • Ludwig Staiger
    Pages 1-10

  3. Properties of Right One-Way Jumping Finite Automata

    • Simon Beier, Markus Holzer
    Pages 11-23

  4. Word Problem Languages for Free Inverse Monoids

    • Tara Brough
    Pages 24-36

  5. Most Complex Deterministic Union-Free Regular Languages

    • Janusz A. Brzozowski, Sylvie Davies
    Pages 37-48

  6. Site-Directed Insertion: Decision Problems, Maximality and Minimality

    • Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. Smith
    Pages 49-61

  7. Two-Way Automata over Locally Finite Semirings

    • Louis-Marie Dando, Sylvain Lombardy
    Pages 62-74

  8. A New Technique for Reachability of States in Concatenation Automata

    • Sylvie Davies
    Pages 75-87

  9. Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs

    • Miguel Ferreira, Nelma Moreira, Rogério Reis
    Pages 88-100

  10. On the Generation of 2-Polyominoes

    • Enrico Formenti, Paolo Massazza
    Pages 101-113

  11. A Local Limit Property for Pattern Statistics in Bicomponent Stochastic Models

    • Massimiliano Goldwurm, Jianyi Lin, Marco Vignati
    Pages 114-125

  12. Linear-Time Limited Automata

    • Bruno Guillon, Luca Prigioniero
    Pages 126-138

  13. Cover Complexity of Finite Languages

    • Stefan Hetzl, Simon Wolfsteiner
    Pages 139-150

  14. On the Grammatical Complexity of Finite Languages

    • Markus Holzer, Simon Wolfsteiner
    Pages 151-162

  15. State Grammars with Stores

    • Oscar H. Ibarra, Ian McQuillan
    Pages 163-174

  16. Error-Free Affine, Unitary, and Probabilistic OBDDs

    • Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz
    Pages 175-187

  17. State Complexity of Unambiguous Operations on Deterministic Finite Automata

    • Galina Jirásková, Alexander Okhotin
    Pages 188-199

  18. Cycle Height of Finite Automata

    • Chris Keeler, Kai Salomaa
    Pages 200-211

  19. Finite Automata with Undirected State Graphs

    • Martin Kutrib, Andreas Malcher, Christian Schneider
    Pages 212-223

  20. Further Closure Properties of Input-Driven Pushdown Automata

    • Alexander Okhotin, Kai Salomaa
    Pages 224-236
Back to top

Other volumes

  1. Descriptional Complexity of Formal Systems

Keywords

About this book

This book constitutes the proceedings of the 20th International Conference on Descriptional Complexity of Formal Systems, DCFS 2018, held in Halifax, NS, Canada, in July 2018. The 19 full papers presented were carefully reviewed and selected from 24 submissions.

DCFS is an annual international working conference concerning the descriptional complexity of formal systems and structures and its applications. Topics of interest are related to all aspects of descriptional complexity and much more. 

Editors and Affiliations

  • Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Canada

    Stavros Konstantinidis

  • Dipartimento di Informatica e Comunicazi, Universita degli Studi di Milano, Milan, Italy

    Giovanni Pighizzini

Bibliographic Information

Publish with us

Policies and ethics

Societies and partnerships

Back to top

Search

Navigation