Skip to main content
SpringerLink
Log in
Book cover

Descriptional Complexity of Formal Systems

16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014, Proceedings

  • Conference proceedings
  • © 2014

Overview

Editors:
  1. Helmut Jürgensen

    1. Department of Computer Science, The University of Western Ontario, London, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Juhani Karhumäki

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Alexander Okhotin

    1. 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 8614)

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

Included in the following conference series:

Conference proceedings info: DCFS 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 (31 papers)

  1. Front Matter

    Download chapter PDF

  2. Recent Developments in Quantum Algorithms and Complexity

    • Andris Ambainis
    Pages 1-4

  3. Automata with Reversal-Bounded Counters: A Survey

    • Oscar H. Ibarra
    Pages 5-22

  4. Star-Free Languages and Local Divisors

    • Manfred Kufleitner
    Pages 23-28

  5. Aperiodic Tilings by Right Triangles

    • Nikolay Vereshchagin
    Pages 29-41

  6. Quantum Hashing via ε-Universal Hashing Constructions and Freivalds’ Fingerprinting Schemas

    • Farid Ablayev, Marat Ablayev
    Pages 42-52

  7. Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs

    • Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryılmaz
    Pages 53-64

  8. Matter and Anti-Matter in Membrane Systems

    • Artiom Alhazov, Bogdan Aman, Rudolf Freund, Gheorghe Păun
    Pages 65-76

  9. Complexity of Extended vs. Classic LR Parsers

    • Angelo Borsotti, Luca Breveglieri, Stefano Crespi Reghizzi, Angelo Morzenti
    Pages 77-89

  10. Most Complex Regular Right-Ideal Languages

    • Janusz Brzozowski, Gareth Davies
    Pages 90-101

  11. State Complexity of Inversion Operations

    • Da-Jung Cho, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
    Pages 102-113

  12. Cycles and Global Attractors of Reaction Systems

    • Enrico Formenti, Luca Manzoni, Antonio E. Porreca
    Pages 114-125

  13. Classical Automata on Promise Problems

    • Viliam Geffert, Abuzer Yakaryılmaz
    Pages 126-137

  14. From Ultrafilters on Words to the Expressive Power of a Fragment of Logic

    • Mai Gehrke, Andreas Krebs, Jean-Éric Pin
    Pages 138-149

  15. Computation Width and Deviation Number

    • Daniel Goč, Kai Salomaa
    Pages 150-161

  16. Boundary Sets of Regular and Context-Free Languages

    • Markus Holzer, Sebastian Jakobi
    Pages 162-173

  17. Biclique Coverings, Rectifier Networks and the Cost of ε-Removal

    • Szabolcs Iván, Ádám D. Lelkes, Judit Nagy-György, Balázs Szörényi, György Turán
    Pages 174-185

  18. Small Universal Non-deterministic Petri Nets with Inhibitor Arcs

    • Sergiu Ivanov, Elisabeth Pelz, Sergey Verlan
    Pages 186-197

  19. A Full and Linear Index of a Tree for Tree Patterns

    • Jan Janoušek, Bořivoj Melichar, Radomír Polách, Martin Poliak, Jan Trávníček
    Pages 198-209

  20. Prefix-Free Languages: Right Quotient and Reversal

    • Jozef Jirásek, Galina Jirásková, Monika Krausová, Peter Mlynárčik, Juraj Šebej
    Pages 210-221
Back to top

Other volumes

  1. Descriptional Complexity of Formal Systems

Keywords

About this book

This book constitutes the refereed proceedings of the 16th International Conference on Descriptional Complexity of Formal Systems, DCFS 2014, held in Turku, Finland, in August 2014. The 27 full papers presented were carefully reviewed and selected from 35 submissions. The conference dealt with the following topics: Automata, grammars, languages and other formal systems; various modes of operation and complexity measures; trade-offs between computational models and modes of operation; succinctness of description of objects, state explosion-like phenomena; circuit complexity of Boolean functions and related measures; resource-bounded or structure-bounded environments; frontiers between decidability and undecidability; universality and reversibility; structural complexity; formal systems for applications (e.g., software reliability, software and hardware testing, modeling of natural languages); nature-motivated (bio-inspired) architectures and unconventional models of computing; complexity aspects of combinatorics on words; Kolmogorov complexity.

Editors and Affiliations

  • Department of Computer Science, The University of Western Ontario, London, Canada

    Helmut Jürgensen

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

    Juhani Karhumäki

  • University of Turku, Turku, Finland

    Alexander Okhotin

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation