Publications


These selected publications (since 2012) are listed in reverse chronological order. Copies of papers will be provided upon request. Publications before 2012 can be found here.

Journal Articles

[1] M. Holzer and S. Jakobi. Minimal and Hyper-Minimal Biautomata. International Journal of Foundations of Computer Science, 27(2):161-185, February 2016.
DOI
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 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 almost-equivalent 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.

[2] M. Holzer and S. Jakobi. Boundary Sets of Regular and Context-Free Languages. Theoretical Computer Science, 610, Part A:59-77, January 2016.
DOI
We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. KLÍMA, L. POLÁK: On biautomata. RAIRO — Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages.

[3] H. Gruber and M. Holzer. From Finite Automata to Regular Expressions and Back-A Summary on Descriptional Complexity. International Journal of Foundations of Computer Science, 26(8):1009-1040, December 2015.
DOI
The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower bounds on the conversion of finite automata to regular expressions and vice versa. As an interesting special case also one-unambiguous regular expressions, a sort of a deterministic version of a regular expression, are considered. We also briefly recall the known bounds for the removal of spontaneous transitions (ε-transitions) on non-ε-free nondeter-ministic devices. Moreover, we report on recent results on the average case descriptional complexity bounds for the conversion of regular expressions to finite automata and new developments on the state elimination algorithm that converts finite automata to regular expressions.

[4] H. Fernau, R. Freund, and M. Holzer. The Finite Index Restriction Meets Hybrid Modes in Cooperating Distributed Grammar Systems. International Journal of Foundations of Computer Science, 26(8):1167-1188, December 2015.
DOI
We study cooperating distributed grammar systems working in hybrid modes in connection with the finite index restriction in two different ways: firstly, we investigate cooperating distributed grammar systems working in hybrid modes which characterize programmed grammars with the finite index restriction; looking at the number of components of such systems, we obtain surprisingly rich lattice structures for the inclusion relations between the corresponding language families. Secondly, we impose the finite index restriction on cooperating distributed grammar systems working in hybrid modes themselves, which leads us to new characterizations of programmed grammars of finite index.

[5] M. Holzer and S. Jakobi. Minimization and Characterizations for Biautomata. Fundamenta Informaticae, 136(1-2):1-25, 2015.
DOI
[6] M. Holzer and S. Jakobi. Nondeterministic Biautomata and Their Descriptional Complexity. International Journal of Foundations of Computer Science, 25(7):837-855, November 2014.
DOI
We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. KLÍMA, L. POLÁK: On biautomata. RAIRO — Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages.

[7] M. Holzer and S. Jakobi. From Equivalence to Almost-Equivalence, and Beyond: Minimizing Automata With Errors. International Journal of Foundations of Computer Science, 24(7):1083-1134, November 2013.
DOI
We introduce E-equivalence, which is a straightforward generalization of almost-equivalence. While almost-equivalence asks for ordinary equivalence up to a finite number of exceptions, in E-equivalence these exceptions or errors must belong to a (regular) set E. The computational complexity of deterministic finite automata (DFAs) minimization problems and their variants w.r.t. almost- and E-equivalence are studied. We show that there is a significant difference in the complexity of problems related to almost-equivalence, and those related to E-equivalence. Moreover, since hyper-minimal and E-minimal automata are not necessarily unique (up to isomorphism as for minimal DFAs), we consider the problem of counting the number of these minimal automata.

[8] H. Gruber and M. Holzer. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science, 24(8):1255-1279, November 2013.
DOI
Based on recent results from extremal graph theory, we prove that every n-state binary deterministic finite automaton can be converted into an equivalent regular expression of size O(1.742n) using state elimination. Furthermore, we give improved upper bounds on the language operations intersection and interleaving on regular expressions.

[9] M. Holzer, M. Kutrib, and K. Meckel. Nondeterministic State Complexity of Star-Free Languages. Theoretical Computer Science, 450:68-80, September 2012.
DOI
We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained by Brzozowski and Liu (2011) for the operation problem of star-free and unary star-free languages accepted by deterministic finite automata.

[10] M. Holzer, S. Jakobi, and M. Kutrib. The Magic Number Problem for Subregular Language Families. International Journal of Foundations of Computer Science, 23(1):115-131, January 2012.
DOI
We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has α states, for all n and α satisfying n<=α<=2n. A number α not satisfying this condition is called a magic number (for n). It was shown that no magic numbers exist for general regular languages, whereas trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, star-free languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic.

[11] M. P. Bianchi, M. Holzer, S. Jakobi, C. Mereghetti, B. Palano, and G. Pighizzini. On Inverse Operations and Their Descriptional Complexity. Journal of Automata, Languages and Combinatorics, 17(2-4):61-81, 2012.
We investigate the descriptional complexity of some inverse language operations applied to languages accepted by finite automata. For instance, the inverse Kleene star operation for a language L asks for the smallest language S such that S* is equal to L, if it exists [J. Brzozowski. Roots of star events. J.ACM 14, 1967]. Other inverse operations, for example based on insertion/deletion operations, can be defined appropriately. We present a general framework, that allows us to give an easy characterization of inverse operations, whenever simple conditions on the originally considered language operation are fulfilled. Concerning the state complexity of some inverse operations, in most cases we obtain exponential upper and lower bounds, while for unary languages tight linear bounds are obtained.

[12] M. Holzer and S. Jakobi. Descriptional Complexity of Chop Operations on Unary and Finite Languages. Journal of Automata, Languages and Combinatorics, 17(2-4):165-183, 2012.
We continue our research on the descriptional complexity of chop operations. Informally, the chop of two words is like their concatenation with the touching letters merged if they are equal, otherwise their chop is undefined. The iterated variants chop-star and chop-plus are defined similar as the classical operations Kleene star and plus. We investigate the state complexity of chop operations on unary and/or finite languages, and obtain similar bounds as for the classical operations. Further, we also show that any chop expression, describing a unary language, can be converted into an equivalent regular expression of linear size, which nicely contrasts the general case.


Books and Invited Papers

[1] M. Holzer and M. Kutrib, editors. Proceedings of the 19th International Conference on Implementation and Application of Automata, number 8587 in LNCS, Giessen, Germany, July-August 2014. Springer.
DOI
[2] H. Gruber and M. Holzer. From Finite Automata to Regular Expressions and Back-A Summary on Descriptional Complexity. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 14th International Conference on Automata and Formal Languages, number 151 in EPTCS, pages 25-48, Szeged, Hungary, May 2014.
DOI
[3] M. Holzer and B. Truthe. Preface. RAIRO-Informatique théorique et Applications / Theoretical Informatics and Applications, 48(1):1-2, January 2014.
DOI
[4] Holzer and M. Kutrib. Self-Assembling Pushdown Automata. Journal of Automata, Languages and Combinatorics, 19(1/4):107-118, 2014.
[5] R. Freund, M. Holzer, and B. Truthe ad U. Ultes-Nitsche. Fourth Workshop on Non-Classical Models for Automata and Applications (NCMA). Number 290 in books@ocg.at. Österreichische Computer Gesellschaft, Vienna, Austria, August 2012.
[6] M. Holzer. A Note on Combined Derivation Modes for Cooperating Distributed Grammar Systems. In H. Bordihn, M. Kutrib, and B. Truthe, editors, Languages Alive-Essays Dedicated to Jürgen Dassow on the Occasion of his 65th Birthday, number 7300 in LNCS, pages 86-98. Springer, 2012.
DOI

Conferences

[1] F. W. Heng, M. Holzer, B. Truthe, S. Turaev, and A. F. Yosman. On Bounded Sequential and Parallel Insertion Systems. In H. Bordihn, R. Freund, B. Nagy, and G. Vaszil, editors, Proceedings of the 8th International Workshop on Non-Classical Models of Automata and Applications, number 321 in books@ocg.at, pages 163-178, Debrecen, Hungary, August 2016. Österreichische Computer Gesellschaft.
[2] H. B. Axelsen, M. Holzer, and M. Kutrib. The Degree of Irreversibility in Deterministic Finite Automata. In Y.-S. Han and K. Salomaa, editors, Proceedings of the 21st Conference on Implementation and Application of Automata, number 9705 in LNCS, pages 15-26, Seoul, South Korea, July 2016. Springer.
DOI
Recently, Holzer et al. gave a method to decide whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA), and eventually proved NL-completeness. Here, we show that the corresponding problem for nondeterministic finite state automata (NFA) is PSPACE-complete. The recent DFA method essentially works by minimizing the DFA and inspecting it for a forbidden pattern. We here study the degree of irreversibility for a regular language, the minimal number of such forbidden patterns necessary in any DFA accepting the language, and show that the degree induces a strict infinite hierarchy of languages. We examine how the degree of irreversibility behaves under the usual language operations union, intersection, complement, concatenation, and Kleene star, showing tight bounds (some asymptotically) on the degree.

[3] H. B. Axelsen, M. Holzer, M. Kutrib, and A. Malcher. Reversible Shrinking Two-Pushdown Automata. In A. H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, editors, Proceedings of the 10th International Conference Language and Automata Theory and Applications, number 9618 in LNCS, pages 579-591, Prague, Czech Republic, March 2016. Springer.
DOI
The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two-pushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and length-reducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking two-pushdown automata, and prove that these are incomparable with the (deterministic) context-free languages. We further show that the properties of emptiness, (in)finiteness, universality, inclusion, equivalence, regularity, and context-freeness are not even semi-decidable for shrinking RTPDAs.

[4] F. Drewes, M. Holzer, S. Jakobi, and B. van der Merwe. Tight Bounds for Cut-Operations on Deterministic Finite Automata. In J. Durand-Lose and B. Nagy, editors, Proceedings of the 7th International Conference Machines, Computations, and Universality, number 9288 in LNCS, pages 45-60, Famagusta, North Cyprus, September 2015. Springer.
DOI
We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (s), answering an open question stated in [M. Berglund, et al.: Cuts in regular expressions. In Proc.DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of (n-1)·m+n states on s accepting the cut of two individual languages that are accepted by n- and m-state s, . In the unary case we obtain max(2n-1,m+n-2) states as a tight bound. For accepting the iterated cut of a language accepted by an n-state we find a matching bound of 1+(n+1)·[]1,n+2,-n+2n+1-1 states on s, where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n-1)!). Finally, the bound drops to 2n-1 for unary s accepting the iterated cut of an n-state and thus is similar to the bound for the cut operation on unary s.

[5] H. Gruber, M. Holzer, and S. Jakobi. More on Deterministic and Nondeterministic Finite Cover Automata. In F. Drewes, editor, Proceedings of the 20th Conference on Implementation and Application of Automata, number 9223 in LNCS, pages 114-126, Umea, Sweden, August 2015. Springer.
DOI
Finite languages are an important sub-regular language family, which were intensively studied during the last two decades in particular from a descriptional complexity perspective. An important contribution to the theory of finite languages are the deterministic and the recently introduced nondeterministic finite cover automata (DFCAs and NFCAs, respectively) as an alternative representation of finite languages by ordinary finite automata. We compare these two types of cover automata from a descriptional complexity point of view, showing that these devices have a lot in common with ordinary finite automata. In particular, we study how to adapt lower bound techniques for nondeterministic finite automata to NFCAs such as, e.g., the biclique edge cover technique, solving an open problem from the literature. Moreover, the trade-off of conversions between DFCAs and NFCAs as well as between finite cover automata and ordinary finite automata are investigated. Finally, we present some results on the average size of finite cover automata.

[6] M. Holzer and S. Jakobi. On the Computational Complexity of Problems Related to Distinguishability Sets. In J. Shallit and A. Okhotin, editors, Proceedings of the 17th Workshop on Deescriptional Complexity of Formal Systems, number 9118 in LNCS, pages 117-128, Waterloo, Ontario, Canada, July 2015. Springer.
DOI
We study the computational complexity of problems related to distinguishability sets for regular languages. Roughly speaking, the distinguishability set D(L) for a (not necessarily regular) language L consists of all words w that are a common suffix of a word xw in L and of a word yw that does not belong to L. In particular, we investigate the complexity of the representation problem, i.e., deciding for given automata A and B, whether B accepts the distinguishability set of L(A). It is shown that this problem and some of its variants are highly intractable, namely -complete. In fact, determining the size of an automaton for D(L(A)) is already -complete. On the other hand, questions related to the hierarchy induced by iterated application of the D-operator turn out to be much easier. For instance, the question whether for a given automaton A, the accepted language is equal to its own distinguishability set, i.e., whether L(A)=D(L(A)) holds, is shown to be -complete. As a byproduct of our investigations, we found a compelling characterization of synchronizing automata, namely that a (minimal) automaton A is synchronizing if and only if D(L(A))=D2(L(A)).

[7] M. Holzer, S. Jakobi, and M. Kutrib. Minimal Reversible Deterministic Finite Automata. In I. Potapov, editor, Proceedings of the 19th International Conference Developments in Language Theory, number 9168 in LNCS, pages 276-287, Liverpool, UK, July 2015. Springer.
DOI
We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to NL-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. Thus, almost all problems that concern uniqueness and the size of minimal REV-DFAs are solved.

[8] M. Holzer and S. Jakobi. Boundary Sets of Regular and Context-Free Languages. In H. Jürgensen, j. Karhumäki, and A. Okhotin, editors, Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems, number 8614 in LNCS, pages 162-173, Turku, Finland, August 2014. Springer.
DOI
We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. The right (left, respectively) a-boundary set of a language L are those words that belong to L, where the a-predecessor or the a-successor of these words w.r.t. the prefix (suffix, respectively) relation is not in L. For regular languages described by deterministic finite automata (DFAs) we give tight bounds on the number of states for accepting boundary sets. Moreover, the question whether the boundary sets of a regular language is finite is shown to be NL-complete for DFAs, while it turns out to be PSPACE-complete for nondeterministic devices. Boundary sets for context-free languages are not necessarily context free anymore. Here we find a subtle difference of right and left a-boundary sets. While right a-boundary sets of deterministic context-free languages stay deterministic context free, we give an example of a deterministic context-free language the left a-boundary set of which is already non context free. In fact, the finiteness problem for a-boundary sets of context-free languages becomes undecidable.

[9] M. Holzer and S. Jakobi. Minimal and Hyper-Minimal Biautomata. In A. M. Shur and M. V. Volkov, editors, Proceedings of the 18th International Conference Developments in Language Theory, number 8633 in LNCS, pages 291-302, Ekaterinburg, Russia, August 2014. Springer.
DOI
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 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 almost-equivalent 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.

[10] M. Holzer, S. Jakobi, and Matthias Wendlandt. On the Computational Complexity of Partial Word Automata Problems. In S. Bensch, R. Freund, and F. Otto, editors, Proceedings of the 6th International Workshop on Non-Classical Models of Automata and Applications, number 304 in books@ocg.at, pages 131-146, Kassel, Germany, July 2014. Österreichische Computer Gesellschaft.
[11] H. Fernau, R. Freund, and M. Holzer. Cooperating Distributed Grammar Systems of Finite Index Working in Hybrid Modes. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 14th International Conference on Automata and Formal Languages, number 151 in EPTCS, pages 246-260, Szeged, Hungary, May 2014.
DOI
We study cooperating distributed grammar systems working in hybrid modes in connection with the finite index restriction in two different ways: firstly, we investigate cooperating distributed grammar systems working in hybrid modes which characterize programmed grammars with the finite index restriction; looking at the number of components of such systems, we obtain surprisingly rich lattice structures for the inclusion relations between the corresponding language families. Secondly, we impose the finite index restriction on cooperating distributed grammar systems working in hybrid modes themselves, which leads us to new characterizations of programmed grammars of finite index.

[12] M. Holzer and S. Jakobi. More Structural Characterizations of Some Subregular Language Families by Biautomata. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 14th International Conference on Automata and Formal Languages, number 151 in EPTCS, pages 271-285, Szeged, Hungary, May 2014.
DOI
We study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the obtained language fami- lies with those induced by deterministic finite automata with the same property. In some cases, it is shown that there is no difference in characterization between deterministic finite automata and biau- tomata as for the permutation-freeness, but there are also other cases, where it makes a big difference whether one considers deterministic finite automata or biautomata. This is, for instance, the case when comparing strongly permutation-freeness, which results in the family of definite language for deterministic finite automata, while biautomata induce the family of finite and co-finite languages. The obtained results nicely fall into the known landscape on classical language families.

[13] E. Formenti, M. Holzer, M. Kutrib, and J. Provillard. ω-Rational Languages: High Complexity Classes vs. Borel Hierarchy. In A. H. Dediu, C. Martín-Vide, J. L. Sierra-Rodríguez, and B. Truthe, editors, Proceedings of the 8th International Conference on Language and Automata Theory and Applications, number 8270 in LNCS, pages 372-282, Madrid, Spain, March 2014. Springer.
DOI
The paper investigates classes of languages of infinite words with respect to the acceptance conditions of the finite automata recognizing them. Some new natural classes are compared with the Borel hierachy. In particular, it is proved that (fin,=) is as high as FRσ and GRσ . As a side effect, it is also proved that in this last case, considering or not considering the initial state of the FA makes a substantial difference.

[14] M. Holzer and S. Jakobi. Minimization and Characterizations for Biautomata. In S. Bensch, F. Drewes, R. Freund, and F. Otto, editors, Proceedings of the 5th International Workshop on Non-Classical Models of Automata and Applications, number 294 in books@ocg.at, pages 179-193, Umeå, Sweden, August 2013. Österreichische Computer Gesellschaft.
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., 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 use the recently introduced notion of nondeterminism for biautomata [M. Holzer, S. Jakobi: Nondeterministic Biautomata and Their Descriptional Complexity. DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.

[15] M. Holzer and S. Jakobi. Brzozowski's Minimization Algorithm-More Robust than Expected (Extended Abstract). In S. Konstantinidis, editor, Proceedings of the 18th International Conference on Implementation and Application of Automata, number 7982 in LNCS, pages 181-192, Halifax, Nova Scotia, Canada, July 2013. Springer.
DOI
For a finite automaton, regardless whether it is deterministic or nondeterministic, Brzozowski’s minimization algorithm computes the equivalent minimal deterministic finite automaton by applying reversal and power-set construction twice. Although this is an exponential algorithm because of the power-set construction, it performs well in experimental studies compared to efficient O(n logn) minimization algorithms. Here we show how to slightly enhance Brzozowski’s minimization algorithm by some sort of reachability information so that it can be applied to the following automata models: deterministic cover automata, almost equivalent deterministic finite state machines, and k-similar automata.

[16] M. Holzer and S. Jakobi. Nondeterministic Biautomata and Their Descriptional Complexity. In H. Jürgensen and R. Reis, editors, Proceedings of the 15th International Workshop on Descriptional Complexity of Formal Systems, number 8031 in LNCS, pages 112-123, London, Ontario, Canada, July 2013. Springer.
DOI
We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. Klíma, L. Polák: On biautomata. RAIRO—Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages.

[17] M. Holzer and S. Jakobi. From Equivalence to Almost-Equivalence, and Beyond-Minimizing Automata with Errors (Extended Abstract). In H.-C. Yen and O. H. Ibarra, editors, Proceedings of the 16th International Conference Developments in Language Theory, number 7410 in LNCS, pages 190-201, Taipei, Taiwan, August 2012. Springer.
DOI
We introduce E-equivalence, which is a straightforward generalization of almost-equivalence. While almost-equivalence asks for ordinary equivalence up to a finite number of exceptions, in E-equivalence these exceptions or errors must belong to a (regular) set E. The computational complexity of minimization problems and their variants w.r.t. almost- and E-equivalence are studied. Roughly speaking, whenever nondeterministic finite automata (NFAs) are involved, most minimization problems, and their equivalence problems they are based on, become PSPACE-complete, while for deterministic finite automata (DFAs) the situation is more subtle. For instance, hyper-minimizing DFAs is NL-complete, but E-minimizing DFA s is NP-complete, even for finite E. The obtained results nicely fit to the known ones on ordinary minimization for finite automata. Moreover, since hyper-minimal and E-minimal automata are not necessarily unique (up to isomorphism as for minimal DFAs), we consider the problem of counting the number of these minimal automata. It turns out that counting hyper-minimal DFAs can be done in FP, while counting E-minimal DFA s is #P-hard, and belongs to the counting class #·coNP.

[18] M. Holzer, S. Jakobi, and I. McQuillan. General Derivations with Synchronzied Context-Free Grammars. In H.-C. Yen and O. H. Ibarra, editors, Proceedings of the 16th International Conference Developments in Language Theory, number 7410 in LNCS, pages 109-120, Taipei, Taiwan, August 2012. Springer.
DOI
Synchronized context-free grammars are special context-free grammars together with a relation which must be satisfied between every pair of paths from root to leaf in a derivation tree, in order to contribute towards the generated language. In the past, only the equality relation and the prefix relation have been studied, with both methods generating exactly the ET0L languages. In this paper, we study arbitrary relations, and in particular, those defined by a transducer. We show that if we use arbitrary a-transducers, we can generate all recursively enumerable languages, and moreover, there exists a single fixed transducer, even over a two letter alphabet, which allows to generate all recursively enumerable languages. We also study the problem over unary transducers. Although it is left open whether or not we can generate all recursively enumerable languages with unary transducers, we are able to demonstrate that we can generate all ET0L languages as well as a language that is not an indexed language. Only by varying the transducer used to define the relation, this generalization is natural, and can give each of the following language families: context-free languages, a family between the E0L and ET0L languages, ET0L languages, and recursively enumerable languages.

[19] M. Holzer and S. Jakobi. State Complexity of Chop Operations on Unary and Finite Languages. In M. Kutrib, N. Moreira, and R. Reis, editors, Proceedings of the 14th Workshop on Descriptional Complexity of Formal Systems, number 7386 in LNCS, pages 169-182, Braga, Portugal, July 2012. Springer.
DOI
We continue our research on the descriptional complexity of chop operations. Informally, the chop of two words is like their concatenation with the touching letters merged if they are equal, otherwise their chop is undefined. The iterated variants chop-star and chop-plus are defined similar as the classical operations Kleene star and plus. We investigate the state complexity of chop operations on unary and/or finite languages, and obtain similar bounds as for the classical operations.

[20] M. P. Bianchi, M. Holzer, S. Jakobi, and G. Pighizzini. On Inverse Operations and Their Descriptional Complexity. In M. Kutrib, N. Moreira, and R. Reis, editors, Proceedings of the 14th Workshop on Descriptional Complexity of Formal Systems, number 7386 in LNCS, pages 89-102, Braga, Portugal, July 2012. Springer.
DOI
We investigate the descriptional complexity of some inverse language operations applied to languages accepted by finite automata. For instance, the inverse Kleene star operation for a language L asks for the smallest language S such that S* is equal to L, if it exists [J. Brzozowski. Roots of star events. J. ACM 14, 1967]. Other inverse operations based on the chop operation or on insertion/deletion operations can be defined appropriately. We present a general framework, that allows us to give an easy characterization of inverse operations, whenever simple conditions on the originally considered language operation are fulfilled. It turns out, that in most cases we obtain exponential upper and lower bounds that are asymptotically close, for the investigated inverse language operation problems.

[21] M. Holzer and S. Jakobi. Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International Conference on FUN with Algorithms, number 7288 in LNCS, pages 223-234, Venice, Italy, June 2012. Springer.
DOI
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 [E. D. Demaine, R. A. Hearn: A uniform framework or modeling computations as games. Proc. CCC, 2008] to Xmas tree mazes.

[22] M. Holzer and S. Jakobi. On the Complexity of Rolling Block and Alice Mazes. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International Conference on FUN with Algorithms, number 7288 in LNCS, pages 210-222, Venice, Italy, June 2012. Springer.
DOI
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 [E. D. Demaine, R. A. Hearn: A uniform framework or modeling computations as games. Proc. CCC, 2008] to the problems in question. By using only blocks of size 2×1×1, and no forbidden squares, we improve a previous result of [K. Buchin, M. Buchin: Rolling block mazes are PSPACE-complete. J. Inform. Proc., 2012] 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.

[23] J. Engel, M. Holzer, O. Ruepp, and F. Sehnke. On Computer Integrated Rationalized Crossword Puzzle Manufactering. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International Conference on FUN with Algorithms, number 7288 in LNCS, pages 131-141, Venice, Italy, June 2012. Springer.
DOI
The crossword puzzle is a classic pastime that is well-known all over the world. We consider the crossword manufacturing process in more detail, investigating a two-step approach, first generating a mask, which is an empty crossword puzzle skeleton, and then filling the mask with words from a given dictionary to obtain a valid crossword. We show that the whole manufacturing process is NP-complete, and in particular also the second step of the two-step manufacturing, thus reproving in part a result of Lewis and Papadimitriou mentioned in Garey and Johnson’s monograph [M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.] but now under real world crossword puzzle conditions. Moreover, we show how to generate high-quality masks via a memetic algorithm, which is used and tested in an industrial manufacturing environment, leading to very good results.


Technical Reports

[1] M. Holzer and S. Jakobi. A Note on the Computational Complexity of Some Problems for Self-Verifying Finite Automata. IFIG Research Report 1501, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, July 2015.
PDF
[2] H. Gruber and M. Holzer. Regular Expressions From Deterministic Finite Automata, Revisited. IFIG Research Report 1403, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, May 2014.
PDF
[3] M. Holzer, S. Jakobi, and M. Wendlandt. On the Complexity of Partial Word Automata Problems. IFIG Research Report 1404, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, May 2014.
PDF
[4] M. Holzer and S. Jakobi. Minimal and Hyper-Minimal Biautomata. IFIG Research Report 1401, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, March 2014.
PDF
[5] M. Holzer and S. Jakobi. Minimization, Characterizations, and Nondeterminism for Biautomata. IFIG Research Report 1301, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, April 2013.
PDF
[6] M. Holzer and S. Jakobi. On the Complexity of Rolling Block and Alice Mazes. IFIG Research Report 1202, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, January 2012.
PDF
[7] M. Holzer and S. Jakobi. Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes. IFIG Research Report 1201, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, January 2012.
PDF

Parts of this pages were generated by bibtex2thml.