IFIG Research Report
Dauerhafte URI für die Sammlung
Stöbern nach
Auflistung IFIG Research Report nach Autor:in "Holzer, Markus"
Gerade angezeigt 1 - 20 von 22
Treffer pro Seite
Sortieroptionen
Item 18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008(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 veranstaltet. Im Laufe des Theorietags findet auch die jährliche Fachgruppensitzung statt. Seit 1996 wird der Theorietag von einem eintägigen Workshop mit eingeladenen Vorträgen begleitet. Die bisherigen Austragungsorte waren Magdeburg (1991), Kiel (1992), Dagstuhl (1993), Herrsching (1994), Schloß Rauischholzhausen (1995), Cunnersdorf (1996), Barnstorf (1997), Riveris (1998), Schauenburg-Elmshagen (1999), Wien (2000), Wendgräben (2001), Wittenberg (2002), Herrsching (2003), Caputh (2004),Lauterbad (2005), Wien (2006) und Leipzig (2007). Der diesjährige Theorietag wird nach 13 Jahren wieder vom Institut für Informatik der Justus-Liebig-Universität Gießen ausgerichtet. Er findet mit dem vorangestellten Workshop über Selected Topics in Theoretical Computer Science vom 30. September bis zum 2. Oktober 2008 in Wettenberg-Launsbach bei Gießen statt. Teilnehmer aus Belgien, Deutschland, England, Frankreich, Italien, Österreich, Tschechien und Ungarn folgten der Einladung nach Mittelhessen.Item A Short Comment on Controlled Context-Free Grammar Derivations(2024-07-04) Holzer, MarkusWe prove that the family of languages generated by regularly controlled grammars with control languages accepted by ordered automata is equal to the family of languages generated by matrix grammars. To our knowledge, this equivalence has been overlooked in the literature.Item Comments on Monoids Induced by NFAs(2023-03) Holzer, MarkusWe 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 their (minimal) number of generators - a comprehensive list of these generators is given in the Appendix. It is shown that any language accepted by an n-state NFA has a syntactic monoid of size at most 2^{n^2}. This bound is reachable by the generators of the semigroup B_n of n x n Boolean matrices with the usual matrix multiplication except that we assume 1 + 1 = 1. The number of these generators grows exponentially in n. This is a significant difference to the deterministic case, where three generators suffice to generate all elements of T_n. Moreover, we prove a lower bound for the \nfa-to-\dfa\ conversion using Lambert's W function.Item Economy of Description for Basic Constructions on Rational Transductions(2002) Bordihn, Henning; Holzer, Markus; Kutrib, MartinItem Flip-Pushdown Automata: k+1 Pushdown Reversals are Better Than k(2002) Holzer, Markus; Kutrib, MartinItem Flip-Pushdown Automata: Nondeterminism is Better Than Determinism(2003) Holzer, Markus; Kutrib, MartinItem Grid graphs with diagonal edges and the complexity of Xmas mazes(2012) Holzer, Markus; Jakobi, SebastianWe 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 game one has to move sticks of a certain length through a maze, ending in a particular game situation. It turns out that when the number of sticks is bounded by some constant, these problems are closely related to the grid graph problems with diagonals. If on the other hand an unbounded number of sticks is allowed, then the problem of solving such a maze becomes PSPACE-complete. Hardness is shown via a reduction from the nondeterministic constraint logic (NCL) of Demaine and Hearn to Xmas tree mazes.Item Improving Raster Image Run-Length Encoding Using Data Order(2001) Holzer, Markus; Kutrib, MartinItem Minimal and hyper-minimal biautomata(2014) Holzer, Markus; Jakobi, SebastianWe 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 hyper-minimization problem. Concerning classical minimality, the known results such as isomorphism between minimal DFAs, and NL-completeness of the DFA minimization problem carry over to the biautomaton case. But surprisingly this is not the case for hyper-minimization: the similarity between almostequivalent hyper-minimal biautomata is not as strong as it is between almost-equivalent hyper-minimal DFAs. Moreover, while hyper-minimization is NL-complete for DFAs, we prove that this problem turns out to be computationally intractable, i.e., NP-complete, for biautomata.Item Minimization, characterizations, and nondeterminism for biautomata(2013) Holzer, Markus; Jakobi, SebastianWe 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., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first generalize the notion of biautomata to deal with nondeterminism and moreover, to take structural properties of the forward- and backward-transition of the automaton into account. This results in a variety of biautomata models, which accepting power is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.Item Nondeterministic Descriptional Complexity of Regular Languages(2002) Holzer, Markus; Kutrib, MartinItem A note on the computational complexity of some problems for self-verifying finite automata(2017) Holzer, Markus; Jakobi, SebastianWe 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 Formal Systems 2015 held in Waterloo, Ontario, Canada, on the complexity of the promise version of the general membership problem for svFAs, showing that this problem is NL-complete.Item On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem(2024-06-27) Gruber, Hermann; Holzer, Markus; Rauch, ChristianThis paper complements a recent inapproximability result for the minimal pumping constant w.r.t. a fixed regular pumping lemma for nondeterministic finite automata [H. Gruber and M. Holzer and C. Rauch. The Pumping Lemma for Regular Languages is Hard. CIAA 2023, pp. 128-140.], by showing the inapproximability of this problem even for deterministic finite automata, and at the same time proving stronger lower bound on the attainable approximation ratio, assuming the Exponential Time Hypothesis (ETH). To that end, we describe those homomorphisms that, in a precise sense, preserve the respective pumping arguments used in two different pumping lemmata. We show that, perhaps surprisingly, this concept coincides with the classic notion of star height preserving homomorphisms as studied by McNaughton, and by Hashiguchi and Honda in the 1970s. Also, we gain a complete understanding of the minimal pumping constant for bideterministic finite automata, which may be of independent interest.Item On the complexity of rolling block and Alice mazes(2012) Holzer, Markus; Jakobi, SebastianWe 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 in the latter one, one has to move tokens of variable speed through a maze following some prescribed directions. It turns out that when the number of blocks or the number of tokens is not restricted (unbounded), then the problem of solving such a maze becomes PSPACE-complete. Hardness is shown via a reduction from the nondeterministic constraint logic (NCL) of Demaine and Hearn to the problems in question. In this way we improve on a previous PSPACE-completeness result of Buchin and Buchin on rolling block mazes to best possible. Moreover, we also consider bounded variants of these maze games, i.e., when the number of blocks or tokens is bounded by a constant, and prove close relations to variants of graph reachability problems.Item On the computational complexity of partial word automata problems(2014) Holzer, Markus; Jakobi, Sebastian; Wendlandt, MatthiasItem On the descriptional complexity of operations on semilinear sets(2017) Beier, Simon; Holzer, Markus; Kutrib, MartinWe 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 of a semilinear set are: (i) the maximal value that appears in the vectors of periods and constants and (ii) the number of such sets of periods and constants necessary to describe the semilinear set under consideration. More precisely, we prove upper bounds on the union, intersection, complementation, and inverse homomorphism. In particular, our result on the complementation upper bound answers an open problem from [G. J. Lavado, G. Pighizzini, S. Seki: Operational State Complexity of Parikh Equivalence, 2014].Item On the magic number problem of the cut operation(2017) Holzer, Markus; Hospodár, MichalWe 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 cut operation and show that the entire range of complexities, up to the known upper bound, can be produced in case of binary alphabets. Moreover, we prove that in the unary case only complexities up to 2m-1 and between n and m+n-2 can be produced, while if 2m<=n-1, then complexities within the interval 2m up to n-1 cannot be reached---these non-producible numbers are called ´magic´.Item Properties of right one-way jumping finite automata(2018) Beier, Simon; Holzer, MarkusRight 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 that process the input in a discontinuous way with the restriction that the input head reads deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We solve most of the open problems of these devices. In particular, we characterize the family of permutation closed languages accepted by ROWJFAs in terms of Myhill-Nerode equivalence classes. Using this, we investigate closure and non-closure properties as well as inclusion relations to other language families. We also give more characterizations of languages accepted by ROWJFAs for some interesting cases.Item Semi-Linear Lattices and Right One-Way Jumping Finite Automata(2019) Beier, Simon; Holzer, MarkusRight 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. In Proc. 20th DCFS, number 10952 in LNCS, 2018] it was shown that the permutation closed languages accepted by ROWJFAs are exactly that with a finite number of positive Myhill-Nerode classes. Here a Myhill-Nerode equivalence class [w]_L of a language L is said to be positive if w belongs to L. Obviously, this notion of positive Myhill-Nerode classes generalizes to sets of vectors of natural numbers. We give a characterization of the linear sets of vectors with a finite number of positive Myhill-Nerode classes, which uses rational cones. Furthermore, we investigate when a set of vectors can be decomposed as a finite union of sets of vectors with a finite number of positive Myhill-Nerode classes. A crucial role play lattices, which are special semi-linear sets that are defined as a natural way to extend ´the pattern´ of a linear set to the whole set of vectors of natural numbers in a given dimension. We show deep connections of lattices to the Myhill-Nerode relation and to rational cones. Some of these results will be used to give characterization results about ROWJFAs with multiple initial states. For binary alphabets we show connections of these and related automata to counter automata.Item State Complexity of Basic Operations on Nondeterministic Finite Automata(2001) Holzer, Markus; Kutrib, Martin