Skip to main content
SpringerLink
Log in
Book cover

Descriptional Complexity of Formal Systems

15th International Workshop, DCFS 2013, London, Canada, July 22-25, 2013, Proceedings

  • Conference proceedings
  • © 2013

Overview

Editors:
  1. Helmut Jurgensen

    1. Department of Computer Science, Middlesex College, Western University, London, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rogério Reis

    1. Departamento de Ciência de Computadores, Universidade do Porto, Faculdade de Ciências, Porto, Portugal

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Fast track conference proceedings
  • Unique visibility
  • State of the art research

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

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

Included in the following conference series:

Conference proceedings info: DCFS 2013.

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

  1. Front Matter

    Download chapter PDF

  2. Blum Static Complexity and Encoding Spaces

    • Cezar Câmpeanu
    Pages 1-13

  3. Millstream Systems and Graph Transformation for Complex Linguistic Models

    • Frank Drewes
    Pages 14-16

  4. Can Chimps Go It Alone?

    • Pierre McKenzie
    Pages 17-17

  5. Invertible Transductions and Iteration

    • Klaus Sutner
    Pages 18-29

  6. Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star

    • Janusz Brzozowski, David Liu
    Pages 30-41

  7. Searching for Traces of Communication in Szilard Languages of Parallel Communicating Grammar Systems - Complexity Views

    • Liliana Cojocaru, Erkki Mäkinen
    Pages 42-53

  8. State Complexity of Basic Operations on Non-returning Regular Languages

    • Hae-Sung Eom, Yo-Sub Han, Galina Jirásková
    Pages 54-65

  9. State Complexity of Subtree-Free Regular Tree Languages

    • Hae-Sung Eom, Yo-Sub Han, Sang-Ki Ko
    Pages 66-77

  10. State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

    • Hae-Sung Eom, Yo-Sub Han, Kai Salomaa
    Pages 78-89

  11. A Direct Construction of Finite State Automata for Pushdown Store Languages

    • Viliam Geffert, Andreas Malcher, Katja Meckel, Carlo Mereghetti, Beatrice Palano
    Pages 90-101

  12. Nondeterministic State Complexity of Proportional Removals

    • Daniel Goč, Alexandros Palioudakis, Kai Salomaa
    Pages 102-111

  13. Nondeterministic Biautomata and Their Descriptional Complexity

    • Markus Holzer, Sebastian Jakobi
    Pages 112-123

  14. Queue Automata of Constant Length

    • Sebastian Jakobi, Katja Meckel, Carlo Mereghetti, Beatrice Palano
    Pages 124-135

  15. On the State Complexity of the Reverse of \({\mathcal R}\)- and \({\mathcal J}\)-Trivial Regular Languages

    • Galina Jirásková, Tomáš Masopust
    Pages 136-147

  16. Size of Unary One-Way Multi-head Finite Automata

    • Martin Kutrib, Andreas Malcher, Matthias Wendlandt
    Pages 148-159

  17. Syntactic Complexity of \({\mathcal R}\)- and \({\mathcal J}\)-Trivial Regular Languages

    • Janusz Brzozowski, Baiyu Li
    Pages 160-171

  18. Sophistication as Randomness Deficiency

    • Francisco Mota, Scott Aaronson, Luís Antunes, André Souto
    Pages 172-181

  19. Shortest Repetition-Free Words Accepted by Automata

    • Hamoon Mousavi, Jeffrey Shallit
    Pages 182-193

  20. A Characterisation of NL/poly via Nondeterministic Finite Automata

    • Rob Myers, Henning Urbat
    Pages 194-204
Back to top

Other volumes

  1. Descriptional Complexity of Formal Systems

Keywords

About this book

This book constitutes the refereed proceedings of the 15th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2013, held in London, ON, Canada, in July 2013. The 22 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 46 submissions.
The topics covered are automata, grammars, languages and other formal systems; various modes of operations and complexity measures; co-operating systems; succinctness of description of objects, state-explosion-like phenomena; circuit complexity of Boolean functions and related measures; size complexity and structural complexity of formal systems; trade-offs between computational models and mode of operation; applications of formal systems; for instance in software and hardware testing, in dialogue systems, in systems modeling or in modeling natural languages; and their complexity constraints; size or structural complexity of formal systems for modeling natural languages; complexity aspects related to the combinatorics of words; descriptional complexity in resource-bounded or structure-bounded environments; structural complexity as related to descriptional complexity; frontiers between decidability and undecidability; universality and reversibility; nature-motivated (bio-inspired) architectures and unconventional models of computing; Kolmogorov-Chaitin complexity, algorithmic information.

Editors and Affiliations

  • Department of Computer Science, Middlesex College, Western University, London, Canada

    Helmut Jurgensen

  • Departamento de Ciência de Computadores, Universidade do Porto, Faculdade de Ciências, Porto, Portugal

    Rogério Reis

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation