Auflistung IFIG Research Report nach Autor "Holzer, Markus"
Anzeige der Dokumente 1-20 von 20
-
18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008
Holzer, Markus; Kutrib, Martin; Malcher, Andreas (2008)Der Theorietag ist die Jahrestagung der Fachgruppe Automaten und Formale Sprachen der Gesellschaft für Informatik. Er wird seit 1991 von Mitgliedern der Fachgruppe an wechselnden Orten in Deutschland und Österreich ... -
Comments on Monoids Induced by NFAs
Holzer, Markus (2023-03)We summarize known results on the transformation monoid of nondeterministic finite automata (NFAs) from semigroup theory. In particular, we list what is known from the literature on the size of monoids induced by NFAs and ... -
Economy of Description for Basic Constructions on Rational Transductions
Bordihn, Henning; Holzer, Markus; Kutrib, Martin (2002) -
Flip-Pushdown Automata: k+1 Pushdown Reversals are Better Than k
Holzer, Markus; Kutrib, Martin (2002) -
Flip-Pushdown Automata: Nondeterminism is Better Than Determinism
Holzer, Markus; Kutrib, Martin (2003) -
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 ... -
Improving Raster Image Run-Length Encoding Using Data Order
Holzer, Markus; Kutrib, Martin (2001) -
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., ... -
Nondeterministic Descriptional Complexity of Regular Languages
Holzer, Markus; Kutrib, Martin (2002) -
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) -
On the descriptional complexity of operations on semilinear sets
Beier, Simon; Holzer, Markus; Kutrib, Martin (2017)We investigate the descriptional complexity of operations on semilinear sets. Roughly speaking, a semilinear set is the finite union of linear sets, which are built by constant and period vectors. The interesting parameters ... -
On the magic number problem of the cut operation
Holzer, Markus; Hospodár, Michal (2017)We investigate the state complexity of languages resulting from the cut operation of two regular languages represented by deterministic finite automata with m and n states, resp. We study the magic number problem of the ... -
Properties of right one-way jumping finite automata
Beier, Simon; Holzer, Markus (2018)Right one-way jumping finite automata (ROWJFAs), were recently introduced in [H. Chigahara, S.Z. Fazekas, A. Yamamura: One-Way Jumping Finite Automata, Internat. J. Found. Comput. Sci., 27(3), 2016] and are jumping automata ... -
Semi-Linear Lattices and Right One-Way Jumping Finite Automata
Beier, Simon; Holzer, Markus (2019)Right one-way jumping automata (ROWJFAs) are an automaton model that was recently introduced for processing the input in a discontinuous way. In [S. Beier, M. Holzer: Properties of right one-way jumping finite automata. ... -
State Complexity of Basic Operations on Nondeterministic Finite Automata
Holzer, Markus; Kutrib, Martin (2001) -
Tight bounds on the descriptional complexity of regular expressions
Gruber, Hermann; Holzer, Markus (2009)We improve on some recent results on lower bounds for conversion problems for regular expressions. In particular we consider the conversion of planar deterministic finite automata to regular expressions, study the effect ... -
Unary Language Operations and Their Nondeterministic State Complexity
Holzer, Markus; Kutrib, Martin (2001)