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 HyperMinimal Biautomata.
International Journal of Foundations of Computer Science,
27(2):161185, February 2016.
DOI We compare deterministic finite automata (DFAs) and biautomata under the following two aspects: structural similarities between minimal and hyperminimal automata, and computational complexity of the minimization and hyperminimization problem. Concerning classical minimality, the known results such as isomorphism between minimal DFAs, and NLcompleteness of the DFA minimization problem carry over to the biautomaton case. But surprisingly this is not the case for hyperminimization: the similarity between almostequivalent hyperminimal biautomata is not as strong as it is between almostequivalent hyperminimal DFAs. Moreover, while hyperminimization is NLcomplete for DFAs, we prove that this problem turns out to be computationally intractable, i.e., NPcomplete, for biautomata.

[2] 
M. Holzer and S. Jakobi.
Boundary Sets of Regular and ContextFree Languages.
Theoretical Computer Science, 610, Part A:5977, 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 blowup 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 BackA Summary
on Descriptional Complexity.
International Journal of Foundations of Computer Science,
26(8):10091040, 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 oneunambiguous 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 nondeterministic 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):11671188, 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(12):125, 2015.
DOI 
[6] 
M. Holzer and S. Jakobi.
Nondeterministic Biautomata and Their Descriptional Complexity.
International Journal of Foundations of Computer Science,
25(7):837855, 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 blowup 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 AlmostEquivalence, and Beyond: Minimizing
Automata With Errors.
International Journal of Foundations of Computer Science,
24(7):10831134, November 2013.
DOI We introduce Eequivalence, which is a straightforward generalization of almostequivalence. While almostequivalence asks for ordinary equivalence up to a finite number of exceptions, in Eequivalence 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 Eequivalence are studied. We show that there is a significant difference in the complexity of problems related to almostequivalence, and those related to Eequivalence. Moreover, since hyperminimal and Eminimal 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):12551279, November 2013.
DOI Based on recent results from extremal graph theory, we prove that every nstate 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 StarFree Languages.
Theoretical Computer Science, 450:6880, September 2012.
DOI We investigate the nondeterministic state complexity of several operations on finite automata accepting starfree and unary starfree 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 starfree and unary starfree 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):115131, January 2012.
DOI We investigate the magic number problem, that is, the question whether there exists a minimal nstate nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has α states, for all n and α satisfying n<=α<=2^{n}. 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 nontrivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, starfree languages, prefix, suffix, and infixclosed languages, and prefix, suffix, and infixfree 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 nonmagic.

[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(24):6181, 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(24):165183, 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 chopstar and chopplus 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, JulyAugust 2014. Springer.
DOI 
[2] 
H. Gruber and M. Holzer.
From Finite Automata to Regular Expressions and BackA 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 2548, Szeged, Hungary, May 2014.
DOI 
[3] 
M. Holzer and B. Truthe.
Preface.
RAIROInformatique théorique et Applications / Theoretical
Informatics and Applications, 48(1):12, January 2014.
DOI 
[4]  Holzer and M. Kutrib. SelfAssembling Pushdown Automata. Journal of Automata, Languages and Combinatorics, 19(1/4):107118, 2014. 
[5]  R. Freund, M. Holzer, and B. Truthe ad U. UltesNitsche. Fourth Workshop on NonClassical 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
AliveEssays Dedicated to Jürgen Dassow on the Occasion of his 65th
Birthday, number 7300 in LNCS, pages 8698. 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 NonClassical Models of Automata and Applications, number 321 in books@ocg.at, pages 163178, 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 1526, 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 (REVDFA), and eventually proved NLcompleteness. Here, we show that the corresponding problem for nondeterministic finite state automata (NFA) is PSPACEcomplete. 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 TwoPushdown Automata.
In A. H. Dediu, J. Janoušek, C. MartínVide, and B. Truthe,
editors, Proceedings of the 10th International Conference Language and
Automata Theory and Applications, number 9618 in LNCS, pages 579591,
Prague, Czech Republic, March 2016. Springer.
DOI The deterministic shrinking twopushdown automata characterize the deterministic growing contextsensitive languages, known to be the ChurchRosser languages. Here, we initiate the investigation of reversible twopushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and lengthreducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking twopushdown automata, and prove that these are incomparable with the (deterministic) contextfree languages. We further show that the properties of emptiness, (in)finiteness, universality, inclusion, equivalence, regularity, and contextfreeness are not even semidecidable for shrinking RTPDAs.

[4] 
F. Drewes, M. Holzer, S. Jakobi, and B. van der Merwe.
Tight Bounds for CutOperations on Deterministic Finite
Automata.
In J. DurandLose and B. Nagy, editors, Proceedings of the 7th
International Conference Machines, Computations, and Universality, number
9288 in LNCS, pages 4560, 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 (n1)·m+n states on s accepting the cut of two individual languages that are accepted by n and mstate s, . In the unary case we obtain max(2n1,m+n2) states as a tight bound. For accepting the iterated cut of a language accepted by an nstate we find a matching bound of 1+(n+1)·[]1,n+2,n+2n+11 states on s, where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n1)!). Finally, the bound drops to 2n1 for unary s accepting the iterated cut of an nstate 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
114126, Umea, Sweden, August 2015. Springer.
DOI Finite languages are an important subregular 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 tradeoff 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 117128, 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 Doperator 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))=D^{2}(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
276287, Liverpool, UK, July 2015. Springer.
DOI We study reversible deterministic finite automata (REVDFAs), 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 REVDFAs. 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 REVDFAs among all equivalent REVDFAs can be decided. Both forbidden pattern characterizations give rise to NLcomplete decision algorithms. In fact, our techniques allow us to construct the minimal REVDFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REVDFAs. Thus, almost all problems that concern uniqueness and the size of minimal REVDFAs are solved.

[8] 
M. Holzer and S. Jakobi.
Boundary Sets of Regular and ContextFree 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 162173, Turku, Finland,
August 2014. Springer.
DOI We investigate the descriptional and computational complexity of boundary sets of regular and contextfree languages. The right (left, respectively) aboundary set of a language L are those words that belong to L, where the apredecessor or the asuccessor 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 NLcomplete for DFAs, while it turns out to be PSPACEcomplete for nondeterministic devices. Boundary sets for contextfree languages are not necessarily context free anymore. Here we find a subtle difference of right and left aboundary sets. While right aboundary sets of deterministic contextfree languages stay deterministic context free, we give an example of a deterministic contextfree language the left aboundary set of which is already non context free. In fact, the finiteness problem for aboundary sets of contextfree languages becomes undecidable.

[9] 
M. Holzer and S. Jakobi.
Minimal and HyperMinimal 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 291302, Ekaterinburg, Russia, August 2014. Springer.
DOI We compare deterministic finite automata (DFAs) and biautomata under the following two aspects: structural similarities between minimal and hyperminimal automata, and computational complexity of the minimization and hyperminimization problem. Concerning classical minimality, the known results such as isomorphism between minimal DFAs, and NLcompleteness of the DFA minimization problem carry over to the biautomaton case. But surprisingly this is not the case for hyperminimization: the similarity between almostequivalent hyperminimal biautomata is not as strong as it is between almostequivalent hyperminimal DFAs. Moreover, while hyperminimization is NLcomplete for DFAs, we prove that this problem turns out to be computationally intractable, i.e., NPcomplete, 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 NonClassical Models of Automata and Applications, number 304 in books@ocg.at, pages 131146, 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 246260, 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 271285, Szeged, Hungary, May 2014.
DOI We study structural restrictions on biautomata such as, e.g., acyclicity, permutationfreeness, strongly permutationfreeness, 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 permutationfreeness, 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 permutationfreeness, which results in the family of definite language for deterministic finite automata, while biautomata induce the family of finite and cofinite 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ínVide, J. L. SierraRodríguez, and
B. Truthe, editors, Proceedings of the 8th International Conference on
Language and Automata Theory and Applications, number 8270 in LNCS, pages
372282, 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 F^{R}_{σ} and G^{R}_{σ} . 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 NonClassical Models of
Automata and Applications, number 294 in books@ocg.at, pages 179193,
Umeå, Sweden, August 2013. Österreichische Computer Gesellschaft.
We show how to minimize biautomata with a Brzozowskilike algorithm by applying reversal and powerset construction twice. Biautomata were recently introduced in [O. Klíma, L. Polák: On biautomata. RAIROTheor.Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowskilike 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 backwardtransitions 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 AlgorithmMore 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 181192, 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 powerset construction twice. Although this is an exponential algorithm because of the powerset 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 ksimilar 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 112123, 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 blowup 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 AlmostEquivalence, and BeyondMinimizing
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 190201, Taipei, Taiwan, August 2012. Springer.
DOI We introduce Eequivalence, which is a straightforward generalization of almostequivalence. While almostequivalence asks for ordinary equivalence up to a finite number of exceptions, in Eequivalence 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 Eequivalence are studied. Roughly speaking, whenever nondeterministic finite automata (NFAs) are involved, most minimization problems, and their equivalence problems they are based on, become PSPACEcomplete, while for deterministic finite automata (DFAs) the situation is more subtle. For instance, hyperminimizing DFAs is NLcomplete, but Eminimizing DFA s is NPcomplete, even for finite E. The obtained results nicely fit to the known ones on ordinary minimization for finite automata. Moreover, since hyperminimal and Eminimal 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 hyperminimal DFAs can be done in FP, while counting Eminimal DFA s is #Phard, and belongs to the counting class #Â·coNP.

[18] 
M. Holzer, S. Jakobi, and I. McQuillan.
General Derivations with Synchronzied ContextFree 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 109120, Taipei, Taiwan, August 2012. Springer.
DOI Synchronized contextfree grammars are special contextfree 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 atransducers, 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: contextfree 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 169182, 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 chopstar and chopplus 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 89102, 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 223234, 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 PSPACEcomplete. 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 210222, 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 PSPACEcomplete. 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 PSPACEcomplete. 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 131141, Venice, Italy, June 2012. Springer.
DOI The crossword puzzle is a classic pastime that is wellknown all over the world. We consider the crossword manufacturing process in more detail, investigating a twostep 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 NPcomplete, and in particular also the second step of the twostep 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 NPCompleteness. W. H. Freeman and Company, 1979.] but now under real world crossword puzzle conditions. Moreover, we show how to generate highquality 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
SelfVerifying Finite Automata.
IFIG Research Report 1501, Institut für Informatik,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, July 2015.

[2] 
H. Gruber and M. Holzer.
Regular Expressions From Deterministic Finite Automata,
Revisited.
IFIG Research Report 1403, Institut für Informatik,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, May 2014.

[3] 
M. Holzer, S. Jakobi, and M. Wendlandt.
On the Complexity of Partial Word Automata Problems.
IFIG Research Report 1404, Institut für Informatik,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, May 2014.

[4] 
M. Holzer and S. Jakobi.
Minimal and HyperMinimal Biautomata.
IFIG Research Report 1401, Institut für Informatik,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, March 2014.

[5] 
M. Holzer and S. Jakobi.
Minimization, Characterizations, and Nondeterminism for
Biautomata.
IFIG Research Report 1301, Institut für Informatik,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, April 2013.

[6] 
M. Holzer and S. Jakobi.
On the Complexity of Rolling Block and Alice Mazes.
IFIG Research Report 1202, Institut für Informatik,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, January 2012.

[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,
JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen,
Germany, January 2012.

Parts of this pages were generated by bibtex2thml.