Descriptional Complexity of Formal Systems: 21st Ifip Wg 1.02 International Conference, Dcfs 2019, Kosice, Slovakia, July 17-19, 2019, Proceedings

ISBN-13: 9783030232467 / Angielski / Miękka / 2019 / 299 str.

Michal Hospodar; Galina Jiraskova; Stavros Konstantinidis

Spis treści

A General Framework for Sequential Grammars with Control Mechanisms.- Low-Complexity Tilings of the Plane.- Union-Freeness, Deterministic Union-Freeness and Union-Complexity.- Limited Automata: Properties, Complexity and Variants.- Nondeterministic Right One-Way Jumping Finite Automata.- State Complexity of Single-Word Pattern Matching in Regular Languages.- Square, Power, Positive Closure, and Complementation on Star-Free Languages.- Descriptional Complexity of Matrix Simple Semi-Conditional Grammars.- Regulated Tree Automata.- Generalized de Bruijn Words and the State Complexity of Conjugate Sets.- The Syntactic Complexity of Semi-Flower Languages.- Limited Nondeterminism of Input-Driven Pushdown Automata Decidability and Complexity.- Computability on Quasi-Polish Spaces.- NFA-to-DFA Trade-Off for Regular Operations.- State Complexity of Simple Splicing.- Nondeterminism Growth and State Complexity.- Descriptional Complexity of Iterated Uniform Finite State Transducers.- On Classes of Regular Languages Related to Monotone WQOs.- State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages.- Pushdown Automata and Constant Height: Decidability and Bounds.- On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances.- How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory.