ENGLISH

Descriptional Complexity of Formal Systems: 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17–19, 2019, Proceedings

By Stavros Konstantinidis , Michal Hospodár , Galina Jirásková

Book information

Publisher
Springer International Publishing
Year
2019
ISBN
978-3-030-23246-7;978-3-030-23247-4
Language
english
Format
PDF
Filesize
7 MB (7204024 bytes)
Series
Lecture Notes in Computer Science 11612
Edition
1st ed.
Pages
X, 299\309
Time added
2019-09-18 12:19:40
Computer Science; Logics and Meanings of Programs;

Description

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. Front Matter ....Pages i-x A General Framework for Sequential Grammars with Control Mechanisms (Rudolf Freund)....Pages 1-34 Low-Complexity Tilings of the Plane (Jarkko Kari)....Pages 35-45 Union-Freeness, Deterministic Union-Freeness and Union-Complexity (Benedek Nagy)....Pages 46-56 Limited Automata: Properties, Complexity and Variants (Giovanni Pighizzini)....Pages 57-73 Nondeterministic Right One-Way Jumping Finite Automata (Extended Abstract) (Simon Beier, Markus Holzer)....Pages 74-85 State Complexity of Single-Word Pattern Matching in Regular Languages (Janusz A. Brzozowski, Sylvie Davies, Abhishek Madan)....Pages 86-97 Square, Power, Positive Closure, and Complementation on Star-Free Languages (Sylvie Davies, Michal Hospodár)....Pages 98-110 Descriptional Complexity of Matrix Simple Semi-conditional Grammars (Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman)....Pages 111-123 Regulated Tree Automata (Henning Fernau, Martin Vu)....Pages 124-136 Generalized de Bruijn Words and the State Complexity of Conjugate Sets (Daniel Gabric, Štěpán Holub, Jeffrey Shallit)....Pages 137-146 The Syntactic Complexity of Semi-flower Languages (Kitti Gelle, Szabolcs Iván)....Pages 147-157 Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity (Yo-Sub Han, Sang-Ki Ko, Kai Salomaa)....Pages 158-170 Computability on Quasi-Polish Spaces (Mathieu Hoyrup, Cristóbal Rojas, Victor Selivanov, Donald M. Stull)....Pages 171-183 NFA-to-DFA Trade-Off for Regular Operations (Galina Jirásková, Ivana Krajňáková)....Pages 184-196 State Complexity of Simple Splicing (Lila Kari, Timothy Ng)....Pages 197-209 Nondeterminism Growth and State Complexity (Chris Keeler, Kai Salomaa)....Pages 210-222 Descriptional Complexity of Iterated Uniform Finite-State Transducers (Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano)....Pages 223-234 On Classes of Regular Languages Related to Monotone WQOs (Mizuhito Ogawa, Victor Selivanov)....Pages 235-247 State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages (Alexander Okhotin, Elizaveta Sazhneva)....Pages 248-259 Pushdown Automata and Constant Height: Decidability and Bounds (Giovanni Pighizzini, Luca Prigioniero)....Pages 260-271 On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances (Petra Wolf)....Pages 272-284 How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory? (Tomoyuki Yamakami)....Pages 285-297 Back Matter ....Pages 299-299

Similar books