| Description |
1 online resource (x, 299 pages) : illustrations |
| Series |
Lectures notes in computer science ; 11612 |
|
Theoretical Computer Science and General Issues |
|
Lecture notes in computer science ; 11612.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
A general framework for sequential grammars with control mechanisms / Rudolf Freund -- Low-complexity tilings of the plane / Jarkko Kari -- Union-freeness, deterministic union-freeness and union-complexity / Benedek Nagy -- Limited automata : properties, complexity and variants / Giovanni Pighizzini -- Nondeterministic right one-way jumping finite automata / Simon Beier and Markus Holzer -- State complexity of single-word pattern matching in regular languages / Janusz A. Brzozowski, Sylvie Davies, and Abhishek Madan -- Square, power, positive closure, and complementation on star-free languages / Sylvie Davies and Michal Hospodár -- Descriptional complexity of matrix simple semi-conditional grammars / Henning Fernau, Lakshmanan Kuppusamy, and Indhumathi Raman -- Regulated tree automata / Henning Fernau and Martin Vu -- Generalized de Bruijn words and the state complexity of conjugate sets / Daniel Gabric, Štěpán Holub, and Jeffrey Shallit -- The syntactic complexity of semi-flower languages / Kitti Gelle and Szabolcs Iván -- Limited nondeterminism of input-driven pushdown automata : decidability and complexity / Yo-Sub Han, Sang-Ki Ko, and Kai Salomaa -- Computability on quasi-Polish spaces / Mathieu Hoyrup, Cristóbal Rojas, Victor Selivanov, and Donald M. Stull -- NFA-to-DFA trade-off for regular operations / Galina Jirásková and Ivana Krajňáková -- State complexity of simple splicing / Lila Kari and Timothy Ng |
|
Nondeterminism growth and state complexity / Chris Keeler and Kai Salomaa -- Descriptional complexity of iterated uniform finite-state transducers / Martin Kutrib, Andreas Malcher, Carlo Mereghetti, and Beatrice Palano -- On classes of regular languages related to monotone WQOs / Mizuhito Ogawa and Victor Selivanov -- State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages / Alexander Okhotin and Elizaveta Sazhneva -- Pushdown automata and constant height : decidability and bounds / Giovanni Pighizzini and Luca Prigioniero -- On the decidability of finding a positive ILP-instance in a regular set of ILP-instances / Petra Wolf -- How does adiabatic quantum computation fit into quantum automata theory? / Tomoyuki Yamakami |
| Summary |
This book constitutes the proceedings of the 21st International Conference on Descriptional Complexity of Format Systems, DCFS 2019, held in Košice, Slovakia, in July 2019. The 18 full papers presented in this volume were carefully reviewed and selected from 25 submissions. The book also contains 4 invited talks. They deal with all aspects of descriptional complexity and costs of description of objects in various computational models, such as Turing machines, pushdown automata, finite automata, grammars, and others. -- Provided by publisher |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Online resource (SpringerLink, viewed August 2, 2019) |
| Subject |
Formal methods (Computer science) -- Congresses
|
|
Logic design.
|
|
Computer science.
|
|
Artificial intelligence.
|
|
Electronic Data Processing
|
|
Artificial Intelligence
|
|
artificial intelligence.
|
|
Artificial intelligence
|
|
Computer science
|
|
Formal methods (Computer science)
|
|
Logic design
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Hospodár, Michal (Computer scientist), editor
|
|
Jirásková, Galina, editor
|
|
Konstantinidis, Stavros, editor.
|
| ISBN |
9783030232474 |
|
3030232476 |
|
3030232468 |
|
9783030232467 |
|
9783030232481 |
|
3030232484 |
|
