Descriptional complexity of formal systems : 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, proceedings / edited by Michal Hospodár, Galina Jirásková, Stavros Konstantinidis
(Visualizza formato Marc21)
(visualizza in BIBRAME 2.0)
| Creatore: |
DCFS (Workshop) (21st : 2019 : Košice, Slovakia.)
|
| Titolo: |
Descriptional complexity of formal systems : 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, proceedings / edited by Michal Hospodár, Galina Jirásková, Stavros Konstantinidis
|
| Link to work: |
Descriptional complexity of formal systems
|
| Pubblicazione: |
Cham, Switzerland : Springer, 2019
|
| Copyright: | ©2019 |
| Estensione: | 1 online resource (x, 299 pages) : illustrations |
| Tipo formato: | computer |
| Tipo contenuto: | text |
| Tipo supporto: | online resource |
| Disciplina: | 005.1015113 |
| Titolo uniforme di collana: | Lecture notes in computer science ; 11612. |
| LNCS sublibrary. SL 1, Theoretical computer science and general issues. | |
| Classificazione LOC: | QA76.9.L63 D34 2019 |
| QA76.5913 | |
| QA76.63 | |
| Creatori/Collaboratori: | Hospodár, Michal, (Computer scientist), [editor.] |
| Jirásková, Galina, [editor.] | |
| Konstantinidis, Stavros, [editor.] | |
| Contenuto supplementare: | Includes bibliographical references and author index. |
| Nota di contenuto: | 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. | |
| Sommario/riassunto: | 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. -- |
| Collana: | Lectures notes in computer science ; 11612 |
| Theoretical Computer Science and General Issues | |
| Varianti del titolo: | DCFS 2019 |
| ISBN: | 9783030232474 |
| 3030232476 | |
| 3030232468 | |
| 9783030232467 | |
| 9783030232481 | |
| 3030232484 | |
| Formato: | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione: | Inglese |
| Record Nr.: | a13630105 |
| Localizzazioni e accesso elettronico | https://stanford.idm.oclc.org/login?url=http://link.springer.com/10.1007/978-3-030-23247-4 |
| Lo trovi qui: | Stanford University |
| Item: | Permalink to OPAC |
Altra ed. diverso supporto:
Printed edition: 9783030232467
Printed edition: 9783030232481