Vai al contenuto principale della pagina

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 Visualizza cluster
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
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
Formato: Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione: Inglese
Record Nr.: a13630105
Localizzazioni e accesso elettronico
Lo trovi qui: Stanford University
Item: Permalink to OPAC
Altra ed. diverso supporto: Printed edition: 9783030232467 Printed edition: 9783030232481