IFIG Research Reporthttps://jlupub.ub.uni-giessen.de//handle/jlupub/75122024-03-29T11:27:15Z2024-03-29T11:27:15ZComments on Monoids Induced by NFAsHolzer, Markushttps://jlupub.ub.uni-giessen.de//handle/jlupub/155732023-03-22T09:00:56Z2023-03-01T00:00:00ZComments on Monoids Induced by NFAs
Holzer, Markus
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 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.
2023-03-01T00:00:00ZOn the complexity of rolling block and Alice mazesHolzer, MarkusJakobi, Sebastianhttps://jlupub.ub.uni-giessen.de//handle/jlupub/75812022-09-13T10:04:54Z2012-01-01T00:00:00ZOn the complexity of rolling block and Alice mazes
Holzer, Markus; Jakobi, Sebastian
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 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.
2012-01-01T00:00:00Z18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008https://jlupub.ub.uni-giessen.de//handle/jlupub/75832022-09-13T10:08:28Z2008-01-01T00:00:00Z18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008
Holzer, Markus; Kutrib, Martin; Malcher, Andreas
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.
2008-01-01T00:00:00ZDescriptional complexity of pushdown store languagesMalcher, AndreasMeckel, KatjaMereghetti, CarloPalano, Beatricehttps://jlupub.ub.uni-giessen.de//handle/jlupub/75822022-09-13T10:08:42Z2012-01-01T00:00:00ZDescriptional complexity of pushdown store languages
Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice
It is well known that the pushdown store language P(M) of a pushdown automaton (PDA) M i.e., the language consisting of words occurring on the pushdownalong accepting computations of M is a regular language. Here, we design succinct nondeterministic finite automata (NFA) accepting P(M). In detail, an upper bound on the size of an NFA for P(M) is obtained, which is quadratic in the number of states and linear in the number of pushdown symbols of M. Moreover, this upper bound is shown to be asymptotically optimal. Then, several restricted variants of PDA are considered, leading to improved constructions. In all cases, we prove the asymptotical optimality of the size of the resulting NFA. Finally, we apply our results to decidability questions related to PDA, and obtain solutions in deterministic polynomial time.
2012-01-01T00:00:00ZTight bounds on the descriptional complexity of regular expressionsGruber, HermannHolzer, Markushttps://jlupub.ub.uni-giessen.de//handle/jlupub/75772022-09-13T10:04:46Z2009-01-01T00:00:00ZTight bounds on the descriptional complexity of regular expressions
Gruber, Hermann; Holzer, Markus
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 of the complementation operation on the descriptional complexity of regular expressions, and the conversion of regular expressions extended by adding intersection or interleaving to ordinary regular expressions. Almost all obtained lower bounds are optimal, and the presented examples are over a binary alphabet, which is best possible.
2009-01-01T00:00:00ZSimplifying regular expressions : A quantitative perspectiveGruber, HermannGulan, Stefanhttps://jlupub.ub.uni-giessen.de//handle/jlupub/75792022-09-13T10:08:13Z2009-01-01T00:00:00ZSimplifying regular expressions : A quantitative perspective
Gruber, Hermann; Gulan, Stefan
In this work, we consider the efficient simplification of regular expressions. We suggest a quantitative comparison of heuristics for simplifying regular expressions. We propose a new normal form for regular expressions, which outperforms previous heuristics while still being computable in linear time. We apply this normal form to determine an exact bound for the relation between the two most common size measures for regular expressions, namely alphabetic width and reverse polish notation length. Then we proceed to show that every regular expression of alphabetic with n can be converted into a nondeterministic finite automaton with e-transitions of size at most 42 5n + 1, and that this bound is optimal. This provides an exact resolution of a research problem posed by Ilie and Yu, who had obtained lower and upper bounds of 4n -1 and 9n - 1 2, respectively [L. Ilie, S. Yu: Follow automata. Inform. Comput. 186, 2003]. For reverse polish notation length as input size measure, an optimal bound was recently determined [S. Gulan, H. Fernau: An optimal construction of finite automata from regular expressions. In: Proc. FST & TCS, 2008]. We prove that, under mild restrictions, their construction is also optimal when taking alphabetic width as input size measure.
2009-01-01T00:00:00ZCellular automata with sparse communicationKutrib, MartinMalcher, Andreashttps://jlupub.ub.uni-giessen.de//handle/jlupub/75782022-09-13T10:08:35Z2009-01-01T00:00:00ZCellular automata with sparse communication
Kutrib, Martin; Malcher, Andreas
We investigate cellular automata whose internal inter-cell communication is bounded. The communication is quantitatively measured by the number of uses of the links between cells. Bounds on the sum of all communications of a computation as well as bounds on the maximal number of communications that may appear between each two cells are considered. It is shown that even the weakest non-trivial device in question, that is,one-way cellular automata where each two neighboring cells may communicate constantly often only, accept rather complicated languages. We investigate the computational capacity of the devices in question and prove an infinite strict hierarchy depending on the bound on the total number of communications during a computation. Despite their sparse communication even for the weakest devices, by reduction of Hilbert´s tenth problem undecidability of several problems is derived. Finally, the question whether a given real-time one-way cellular automaton belongs to the weakest class is shown to be undecidable. This result can be adapted to answer an open question posed in [Vollmar, R.: Zur Zustandsänderungskomplexität von Zellularautomaten. In: Beiträge zur Theorie der Polyautomaten zweite Folge,Braunschweig (1982) 139 151 (in German)].
2009-01-01T00:00:00ZGrid graphs with diagonal edges and the complexity of Xmas mazesHolzer, MarkusJakobi, Sebastianhttps://jlupub.ub.uni-giessen.de//handle/jlupub/75802022-09-13T10:08:43Z2012-01-01T00:00:00ZGrid graphs with diagonal edges and the complexity of Xmas mazes
Holzer, Markus; Jakobi, Sebastian
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 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.
2012-01-01T00:00:00ZMassively parallel pattern recognition with link failuresLöwe, Jan-ThomasKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/75742022-09-13T10:03:51Z2000-01-01T00:00:00ZMassively parallel pattern recognition with link failures
Löwe, Jan-Thomas; Kutrib, Martin
The capabilities of reliable computations in linear cellular arrays with communication failures are investigated in terms of pattern recognition. The defective processing elements (cells) that cause the misoperations are assumed to behave as follows. Dependent on the result of a self-diagnosis of their communication links they store their working state locally such that it becomes visible to the neighbors. A defective cell is not able to receive information via one of its both links to adjacent cells. The self-diagnosis is run once before the actual computation. Subsequently no more failures may occur in order to obtain a valid computation. We center our attention to patterns that are recognizable very fast, i.e. in real-time. It is well-known that real-time one-way arrays are strictly less powerful than real-time two-way arrays, but there is only little known on the range between these two devices. Here it is shown that the sets of patterns reliably recognizable by real-time arrays with link failures are strictly in between the sets of (intact) one-way and (intact) two-way arrays. Hence, the failures cannot be compensated in general but, on the other hand, do not decrease the computing power to that one of one-way arrays. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1, B.8.1, C.4
2000-01-01T00:00:00ZBelow linear-time : Dimensions versus timeKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/75762022-09-13T10:06:48Z2000-01-01T00:00:00ZBelow linear-time : Dimensions versus time
Kutrib, Martin
Deterministic d-dimensional Turing machines are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form id + r where r E o(id) is a sublinear function. It is shown that for any dimension d >= 1 there exist infinite time hierarchies of separated complexity classes in that range. Moreover, for the corresponding time bounds separated dimension hierarchies are proved. CR Subject Classification (1998): F.1.3, F.1.1, F.4.3
2000-01-01T00:00:00Z