Auflistung Schriftenreihen nach Autor "Jakobi, Sebastian"
Anzeige der Dokumente 1-6 von 6
-
Grid graphs with diagonal edges and the complexity of Xmas mazes
Holzer, Markus; Jakobi, Sebastian (2012)We investigate the computational complexity of some maze problems, namely the reachability problem for (undirected) grid graphs with diagonal edges, and the solvability of Xmas tree mazes. Simply speaking, in the latter ... -
Minimal and hyper-minimal biautomata
Holzer, Markus; Jakobi, Sebastian (2014)We compare deterministic finite automata (DFAs) and biautomata under the following two aspects: structural similarities between minimal and hyper-minimal automata, and computational complexity of the minimization and ... -
Minimization, characterizations, and nondeterminism for biautomata
Holzer, Markus; Jakobi, Sebastian (2013)We show how to minimize biautomata with a Brzozowski-like algorithm by applying reversal and powerset construction twice. Biautomata were recently introduced in[O. Klíma, L. Polák: On biautomata. RAIRO Theor. Inf. Appl., ... -
A note on the computational complexity of some problems for self-verifying finite automata
Holzer, Markus; Jakobi, Sebastian (2017)We consider the computational complexity of some problems for self-verifying finite automata (svFAs). In particular, we answer a question stated in the open problem session of the Workshop on Descriptional Complexity of ... -
On the complexity of rolling block and Alice mazes
Holzer, Markus; Jakobi, Sebastian (2012)We investigate the computational complexity of two maze problems, namely rolling block and Alice mazes. Simply speaking, in the former game one has to roll blocks through a maze, ending in a particular game situation, and ... -
On the computational complexity of partial word automata problems
Holzer, Markus; Jakobi, Sebastian; Wendlandt, Matthias (2014)