Publications
These selected publications (before 2005) are listed in reverse chronological order. Copies of papers will be provided upon request. Publications since 2005 can be found here.
Journal Articles
[1] 
M. Holzer and W. Holzer.
Tantrix^{TM} Rotation Puzzles are
Intractable.
Discrete Applied Mathematics, 144(3):345358, December 2004.
DOI It is shown that the Tantrix rotation puzzle can be used to emulate a circuit with AND and NOTgates. In particular, a rotation puzzle is constructed, that has a solution if and only if there exists an assignment to the input variables such that the corresponding circuit evaluates to true. This shows that the rotation puzzle is intractable, i.e., NPcomplete. Moreover, we also consider infinite Tantrix rotation puzzles. Based on a circuit construction, too, we show that in this case the problem becomes even worse, namely undecidable.

[2] 
M. Holzer and B. König.
On Deterministic Finite Automata and Syntactic Monoid Size.
Theoretical Computer Science, 327(3):319347, November 2004.
DOI We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of nstate (minimal) deterministic finite automata. We show tight upper and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used. It turns out, that the two generator case is the most involved one. There we show a lower bound of n^{n}(1(2)/(sqrt(n))) for the size of the syntactic monoid of a language accepted by an nstate deterministic finite automaton with binary input alphabet. Moreover, we prove that for every prime n>=7, the maximal size semigroup w.r.t.its size among all (transformation) semigroups which can be generated with two generators, is generated by a permutation with two cycles (of appropriate lengths) and a nonbijective mapping merging elements from these two cycles. As a byproduct of our investigations we determine the maximal size among all semigroups generated by two transformations, where one is a permutation with a single cycle and the other is a nonbijective mapping.

[3] 
M. Holzer and St. Schwoon.
Assembling Molecules in Atomix is Hard.
Theoretical Computer Science, 313(3):447462, February 2004.
DOI It is shown that assembling molecules in the Atomix game can be used to simulate finite automata. In particular, an instance of Atomix is constructed that has a solution if and only if the nonemptiness intersection problem for finite automata is solvable. This shows that the game under consideration is PSPACEcomplete, improving a recent result of HÃ¼ffner et al. (Lecture Notes in Computer Science, Vol. 2174, Springer, Vienna, Austria, 2001, pp. 229â€“243). Moreover, the given reduction shows that there are Atomix games which have exponentially long optimal solutions. We also give an easy construction of Atomix game levels whose optimal solutions meet the worst case.

[4]  H. Bordihn, M. Holzer, and M. Kutrib. Economy of Description for Basic Constructions on Rational Transductions. Journal of Automata, Languages and Combinatorics, 9(2/3):175188, 2004. 
[5] 
M. Holzer and M. Kutrib.
Nondeterministic Descriptional Complexity of Regular Languages.
International Journal of Foundations of Computer Science,
14(6):10871102, December 2003.
DOI We investigate the descriptional complexity of operations on finite and infinite regular languages over unary and arbitrary alphabets. The languages are represented by nondeterministic finite automata (NFA). In particular, we consider Boolean operations, catenation operationsconcatenation, iteration, λfree iterationand the reversal. Most of the shown bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. Otherwise tight bounds in the order of magnitude are shown.

[6] 
M. Holzer and P. McKenzie.
Alternating and empty alternating auxiliary stack automata.
Theoretical Computer Science, 299(13):307326, April 2003.
DOI We consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. In this way we get new characterizations of , the polynomial hierarchy, , and bounded query classes like =^{[1]} and Θ_{2}=^{[O(log n)]}, in a uniform framework.

[7] 
M. Beaudry, M. Holzer, G. Niemann, and F. Otto.
McNaughton Families of Languages.
Theoretical Computer Science, 290:15811628, 2003.
DOI In 1988 the ChurchRosser languages were introduced by McNaughton et al. as those languages that are recognized by finite, lengthreducing and confluent stringrewriting systems using extra nonterminal symbols. Here we generalize this concept by considering classes of languages that are obtained by other types of stringrewriting systems. To honour Robert McNaughton's original contribution we call the resulting families of languages McNaughton families. Here it is shown that the concept of McNaughton families is as powerful as the notion of Turing machine or the notion of phrasestructure grammar. We investigate the relationships between the various McNaughton families, obtaining an extensive hierarchy of classes that includes many wellknown language and complexity classes as well as some new classes. Further, we consider some closure and nonclosure properties for those McNaughton families that are contained in the class of contextfree languages, and we address the complexity of the fixed and the general membership problems for these families.

[8] 
C. Damm, M. Holzer, and P. McKenzie.
The Complexity of Tensor Calculus.
Computational Complexity, 11(1/2):5489, January 2003.
DOI 
[9]  H. Fernau, R. Freund, and M. Holzer. Hybrid modes in cooperating distributed grammar systems: combining the tmode with the modes <=k and =k. Theoretical Computer Science, 299(13):633662, 2003. 
[10]  H. Bordihn, H. Fernau, and M. Holzer. Accepting Pure Grammars. Publicationes Mathematicae Debrecen, 60(Supplementum):483510, 2002. 
[11] 
M. Holzer.
MultiHead Finite Automata: DataIndependent Versus
DataDependent Computations.
Theoretical Computer Science, 286:97116, 2002.
DOI We develop a multihead finite automata framework suitable for a more detailed study of the relationship between parallel logarithmic time and sequential logarithmic space, in the uniform and nonuniform settings. In both settings it turns out that NC1 requires dataindependent or oblivious computations, i.e., the movement of the inputheads only depends on the length of the input, whereas logarithmic space is captured with datadependent computations on multihead finite state machines. This sheds new light on the question whether NC1 and logarithmic space coincide.

[12]  H. Fernau, R. Freund, and M. Holzer. Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization. Theoretical Computer Science, 259(12):405426, May 2001. 
[13]  H. Bordihn and M. Holzer. On the Number of Active Symbols in L and CD Grammar Systems. Journal of Automata, Languages and Combinatorics, 6(4):411426, 2001. 
[14]  M. Holzer, K. Salomaa, and S. Yu. On the State Complexity of kEntry Deterministic Finite Automata. Journal of Automata, Languages and Combinatorics, 6(4):453466, 2001. 
[15] 
H. Bordihn and M. Holzer.
Grammar Systems with Negated Conditions in Their Cooperation
Protocols.
Journal of Universal Computer Science, 6(12):11651184, 2000.
PDF PS The investigation on Boolean operations on the stop conditions of derivation modes for cooperating distributed grammar systems is continued by considering the logical negation of such conditions. The focus is on the negation of the tmode of derivation, where such nontcomponents may stop rewriting only if they still have a production applicable to the current sentential form. In many cases, hybrid cooperating distributed grammar systems with nontcomponents turn out to give new characterizations of the class of programmed contextfree languages or recurrent programmed contextfree languages, where the latter class coincides with the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.

[16]  H. Bordihn, H. Fernau, and M. Holzer. On Accepting Pure Lindenmayer Systems. Fundamenta Informaticae, 38:365375, 1999. 
[17] 
H. Bordihn and M. Holzer.
On a hierarchy of languages generated by cooperating distributed
grammar systems.
Information Processing Letters, 69(2):5962, January 1999.
DOI For cooperating distributed grammar systems working in = kmode up to now it is only known that this mode can be simulated by the = k·mode for > 1. In this note we show how to improve this simulation when a termination condition is additionally required, showing that the (t /\= k)mode can be simulated by the (t /\= k + 1)mode if the number of components in the underlying cooperating distributed grammar system is increased by two. A similar result is given for the (t /\<=k)mode.

[18]  H. Fernau and M. Holzer. Bidirectional coorperating distributed grammar systems. Publicationes Mathematicae Debrecen, 54(Supplementum):787806, 1998. 
[19] 
C. Damm, M. Holzer, and P. Rossmanith.
Expressing Uniformity via Oracles.
Theory of Computing Systems, 30(4):355366, July 1997.
DOI We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper: Auniform circuits of logarithmic depth are of the same computational power as DLOGTIMEuniform circuits of logarithmic depth with oracle access to tally sets in A. This characterization does not only apply to classes A such as logarithmic space or polynomial time, but to all in some sense “wellbehaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depthuniformity tradeoffs, and inclusioncompleteness results for tally languages.

[20]  M. Holzer and P. Rossmanith. A simpler grammar for Fibonacci Numbers. The Fibonacci Quarterly, 34(5):465466, November 1996. 
[21] 
C. Damm and M. Holzer.
Inductive Counting for WidthRestricted Branching Programs.
Information and Computation, 130(1):9199, October 1996.
DOI As an application of the inductive counting technique to a circuitlike model, we prove that complementation on nondeterministic branching programs can be done without increasing the width excessively. A consequence of this result is that the class of languages recognized by a generalization of nonuniform finite automata to nonconstant space is closed under complement.

[22] 
H. Fernau, M. Holzer, and H. Bordihn.
Accepting MultiAgent Systems: The Case of Cooperating
Distributed Grammar Systems.
Journal of Computers and Artificial Intelligence,
15(2):123139, 1996.
We consider cooperating distributed (CD) grammar systems and variants thereof as language acceptors. If the CD grammar systems work in the modes >=, <=, =, or *, then their generating capacity equals their accepting capacity. Contrary to this, we obtain a new characterization of the contextsensitive languages by accepting CD grammar systems (with or without λproductions) working in tmode. Moreover, accepting hybrid CD (HCD) grammar systems with λproductions characterize the recursively enumerable languages.

[23]  H. Fernau and M. Holzer. Accepting MultiAgent Systems II. Acta CyberneticaSelected Papers of the Workshop Grammars Systems: Recent Results and Perspectives, Budapest, July 1996, 12(4):361379, 1996. 
Books and Invited Papers
[1]  M. Holzer and B. König. Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other. Bulletin of the European Association for Theoretical Computer Science, 83:139155, June 2004. 
[2]  M. Holzer. Computational Complexity. In C. MartínVide and V. Mitrana, editors, Formal Languages and Applications, number 148 in Studies in Fuzziness and Soft Computing, pages 227247. Springer, 2004. 
[3]  M. Holzer (editor). Workshop `{P}etrinetze' und 13. GI Theorietag `{A}utomaten und {F}ormale {S}prachen'. Technical Report TUMI0322, Institut für Informatik, Technische Universität München, Boltzmannstraße 3, D85748 Garching bei München, Germany, December 2003. 
[4]  M. Holzer. Aspects on the Descriptional Complexity of Finite Automata. In E. CsuhajVarjú, Ch. Kintala, D. Wotschke, and Gy. Vaszil, editors, Proceedings of the 5th International Workshop on Descriptional Complexity of Formal Systems, pages 2641, Budapest, Hungary, July 2003. MTA SZTAKI. 
[5]  W. Brauer, M. Holzer, B. König, and S. Schwoon. The Theory of FiniteState Adventures. Bulletin of the European Association for Theoretical Computer Science, 79:230237, February 2003. 
[6]  H. Bordihn, H. Fernau, and M. Holzer. On Iterated Sequential Transducer. In C. MartinVide and V. Mitrana, editors, Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back, pages 121130. Taylor and Francis, London, 2003. 
[7]  M. Holzer and P. McKenzie. On Auxiliary Pushdown and Stack Automata. SIGACT News, 33(1):3235, March 2002. 
[8] 
H. Bordihn and M. Holzer.
On the Computational Complexity of Synchronized ContextFree
Languages.
Journal of Universal Computer Science, 8(2):119140, 2002.
PDF PS 
[9]  H. Fernau and M. Holzer. External Contextual and Conditional Languages. In C. MartinVide and Gh. Paun, editors, Recent Topics in Mathematical and Computational Linguistics, pages 104120. Romanian Academy, Bucharest, June 2000. 
[10]  M. Holzer. DataIndependent Versus DataDependent Computations on MultiHead Automata. Number 10 in Edition VERSAL. Bertz, December 1998. 
[11]  H. Fernau and M. Holzer. Conditional ContextFree Languages of Finite Index. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages: Control, Cooperation, and Combinatorics, number 1218 in LNCS, pages 1026. Springer, 1997. 
[12]  M. Holzer and K.J. Lange. On the Complexity of Iterated Insertions. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages: Control, Cooperation, and Combinatorics, number 1218 in LNCS, pages 440453. Springer, 1997. 
[13]  M. Holzer (editor). 4. GI Theorietag `{A}utomaten und {F}ormale {S}prachen'. Technical Report WSI9510, WilhelmSchickardInstitut für Informatik, Universität Tübingen, Sand 13, D72076 Tübingen, Germany, May 1995. 
Conferences
[1] 
M. H. ter Beek, E. CsuhajVarjú, M. Holzer, and Gy. Vaszil.
On Competence in CD Grammar Systems.
In C. S. Calude, E. Calude, and M. J. Dinneen, editors,
Proceedings of the 8th International Conference on Developments in Language
Theory, number 3340 in LNCS, pages 7688, Auckland, New Zealand, December
2004. Springer.
DOI We investigate the generative power of cooperating distributed grammar systems (CDGSs), if the cooperation protocol is based on the level of competence on the underlying sentential form. A component is said to be = kcompetent (<=k, >=kcompetent, resp.) on a sentential form if it is able to rewrite exactly k (at most k, at least k, resp.) different nonterminals appearing in that string. In most cases CDGSs working according to the above described cooperation strategy turn out to give new characterizations of the language families based on random context conditions, namely random context (contextfree) languages and the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.

[2] 
H. Bordihn, M. Holzer, and M. Kutrib.
Input Reversals and Iterated Pushdown AutomataA New
Characterization of Khabbaz Geometric Hierarchy of Languages.
In C. S. Calude, E. Calude, and M. J. Dinneen, editors,
Proceedings of the 8th International Conference on Developments in Language
Theory, number 3340 in LNCS, pages 102113, Auckland, New Zealand, December
2004. Springer.
DOI Inputreversal pushdown automata are pushdown automata with the additional power to reverse the unread part of the input. We show that these machines characterize the family of linear contextfree indexed languages, and that k + 1 input reversals are better than k for both deterministic and nondeterministic inputreversal pushdown automata, i.e., there are languages which can be recognized by a deterministic inputreversal pushdown automaton with k + 1 input reversals but which cannot be recognized with k input reversals (deterministic or nondeterministic). In passing, inputreversal finite automata are investigated. Moreover, an inherent relation between inputreversal pushdown automata and controlled linear contextfree languages are shown, leading to an alternative description of Khabbaz geometric hierarchy of languages by inputreversal iterated pushdown automata. Finally, some computational complexity problems for the investigated language families are considered.

[3] 
M. Holzer and M. Kutrib.
Register Complexity of LOOP, WHILE, and
GOTOPrograms.
In M. Margenstern, editor, Proceedings of the 4th
International Conference Machines, Computations and Universality, number
3354 in LNCS, pages 233244, St. Petersburg, Russia, September 2004.
Springer.
DOI We study the register complexity of LOOP, WHILE, and GOTOprograms, that is the number of registers (or variables) needed to compute certain unary (partial) functions from the nonnegative integers to the nonnegative integers. It turns out that the hierarchy of LOOPcomputable (WHILE, and GOTOcomputable, respectively) functions f:N_{0}>N_{0} (partial functions f:N_{0}>N_{0}, respectively) that is induced by the number of registers collapses to a fixed level. In all three cases the first levels are separated. Our results show that there exist universal WHILE and GOTOprograms with a constant number of registers.

[4] 
M. Beaudry, J. M. Fernandez, and M. Holzer.
A Common Algebraic Description for Probabilistic and Quantum
Computation.
In J. Fiala, V. Koubek, and J. Kratochvil, editors, Proceedings
of the 29th Conference on Mathematical Foundations of Computer Science,
number 3153 in LNCS, pages 851862, Prague, Czech Republic, August 2004.
Springer.
DOI Through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this basis we show how to encode a probabilistic or quantum gate array into a sumfree tensor formula which satisfies the conditions of the partial trace problem, and viceversa. In this way complete problems for the classes (promise ) and (promise ) are given when changing the semiring from (^{+},+,·) to the field (,+,·). Moreover, by variants of the problem under consideration, classes like ,, C_{=}, its complement C_{=}, the promise version of Valiant's class , its generalization promise , and unique polytime are captured as problem property and the semiring varies.

[5] 
H. Bordihn, M. Holzer, and M. Kutrib.
Some NonSemiDecidability Problems for Linear and Deterministic
ContextFree Languages.
In M. Domaratzki, A. Okhotin, K. Salomaa, and S. Yu, editors,
Proceedings of the 9th International Conference Implementation and
Application of Automata, number 3317 in LNCS, pages 6879, Queen's
University, Kingston, Ontario, Canada, July 2004. Springer.
DOI We investigate the operation problem for linear and deterministic contextfree languages: Fix an operation on formal languages. Given linear (deterministic, respectively) contextfree languages, is the application of this operation to the given languages still a linear (deterministic, respectively) contextfree language? Besides the classical operations, for which the linear and deterministic contextfree languages are not closed, we also consider the recently introduced root and power operation. We show nonsemidecidability for all of the aforementioned operations, if the underlying alphabet contains at least two letters. The nonsemidecidability and thus the undecidability for the power operation solves an open problem stated in [4].

[6]  H. Bordihn and M. Holzer. Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited. In E. CsuhajVarjú and Gy. Vaszil, editors, Preliminary Proceedings of Grammar Systems Week, pages 6682, Budapest, Hungary, July 2004. MTA SZTAKI. 
[7]  E. D. Demaine, M. Hoffmann, and M. Holzer. PushPushk is PSPACEComplete. In P. Ferragnia and R. Grossi, editors, Proceedings of the 3rd International Conference on FUN with Algorithms, pages 159170, Island of Elba, Italy, May 2004. Edizioni Plus, Universitá di Pisa. 
[8]  M. Holzer, A. Klein, and M. Kutrib. On the NPCompleteness of the Nurikabe Pencil Puzzle and Variants Thereof. In P. Ferragnia and R. Grossi, editors, Proceedings of the 3rd International Conference on FUN with Algorithms, pages 7789, Island of Elba, Italy, May 2004. Edizioni Plus, Universitá di Pisa. 
[9]  M. Holzer St. Schwoon. Reflections on ReflexionComputational Complexity Considerations on a Puzzle Game. In P. Ferragnia and R. Grossi, editors, Proceedings of the 3rd International Conference on FUN with Algorithms, pages 90105, Island of Elba, Italy, May 2004. Edizioni Plus, Universitá di Pisa. 
[10]  M. Holzer and B. König. Deterministic Finite Automata and Syntactic Monoid Size, Continued. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 7th International Conference on Developments in Language Theory, number 2710 in LNCS, pages 349360, Szeged, Hungary, July 2003. Springer. 
[11]  M. Holzer and M. Kutrib. FlipPushdown Automata: Nondeterminism is Better Than Determinism. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 7th International Conference on Developments in Language Theory, number 2710 in LNCS, pages 361372, Szeged, Hungary, July 2003. Springer. 
[12]  M. Holzer and M. Kutrib. State Complexity of Basic Operations on Nondeterministic Finite Automata. In J.M. Champarnaud and D. Maurel, editors, Proceedings of the 7th International Conference Implementation and Application of Automata, number 2608 in LNCS, pages 148157, Tours, France, July 2003. Springer. 
[13]  M. Holzer and M. Kutrib. FlipPushdown Automata: k+1 Pushdown Reversals are Better Than k. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeginger, editors, Proceedings of the 30th International Colloqium on Automata, Languages and Propgramming, number 2719 in LNCS, pages 490501, Eindhoven, The Netherlands, JuneJuly 2003. Springer. 
[14]  M. Holzer and B. König. On Deterministic Finite Automata and Syntactic Monoid Size. In M. Ito and M. Toyama, editors, Proceedings of the 6th International Conference on Developments in Language Theory, number 2450 in LNCS, pages 258269, Kyoto, Japan, September 2002. Springer. 
[15]  M. Holzer and M. Kutrib. Unary Language Operations and Their Nondeterministic State Complexity. In M. Ito and M. Toyama, editors, Proceedings of the 6th International Conference on Developments in Language Theory, number 2450 in LNCS, pages 162172, Kyoto, Japan, September 2002. Springer. 
[16] 
M. Beaudry and M. Holzer.
The Complexity of Tensor Circuit Evaluation.
In J. Sgall, A. Pultr, and P. Kolman, editors, Proceedings of
the 26th Conference on Mathematical Foundations of Computer Science,
number 2136 in LNCS, pages 173185, Mariánské Lázne, Czech
Republic, August 2001. Springer.
DOI The study of tensor calculus over semirings in terms of complexity theory was initiated by Damm et al. in (CCC 2000). Here we first look at tensor circuits, a natural generalization of tensor formulas; we show that the problem of asking whether the output of such circuits is nonzero is complete for the class NE = NTIME(2^O(n)) for circuits over the boolean semiring, E for the field , and analogous results for other semirings. Common sense restrictions such as imposing a logarithmic upper bound on circuit depth are also discussed. Second, we analyze other natural problems concerning tensor formulas and circuits over various semirings, such as asking whether the output matrix is diagonal or a null matrix.

[17]  M. Beaudry, M. Holzer, G. Niemann, and F. Otto. On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy. In W. Kuich, G. Rozenberg, and A. Salomaa, editors, Proceedings of the 5th International Conference Developments in Language Theory, number 2295 in LNCS, pages 340348, Wien, Austria, July 2001. Springer. 
[18]  H. Fernau and M. Holzer. GraphControlled Cooperating Distributed Grammar Systems with Singleton Components. In J. Dassow and D. Wotschke, editors, Proceedings of the 3rd International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Preprint Nr. 16, pages 7990, Wien, Austria, July 2001. Fakultät für Informatik, OttovonGuerickeUniversität Magdeburg. 
[19]  M. Holzer and M. Kutrib. Improving raster image runlength encoding using data order. In B. W. Watson and D. Wood, editors, Proceedings of the 6th International Conference on Implementation and Application of Automata, number 2494 in LNCS, pages 161176, Pretoria, South Africa, July 2001. Springer. 
[20] 
M. Holzer and W. Holzer.
Tantrix^{TM} Rotation Puzzles are
Intractable.
In Proceedings of the 2nd International Conference FUN with
Algorithms 2, pages 165182, Island of Elba, Italy, May 2001. Carleton
Scientific.
It is shown that the Tantrix rotation puzzle can be used to emulate a circuit with AND and NOTgates. In particular, a rotation puzzle is constructed, that has a solution if and only if there exists an assignment to the input variables such that the corresponding circuit evaluates to true. This shows that the rotation puzzle is intractable, i.e., NPcomplete. Moreover, we also consider infinite Tantrix rotation puzzles. Based on an easy circuit construction we show that in this case the problem becomes even worse, namely undecidable.

[21] 
M. Holzer and P. McKenzie.
Alternating and Empty Alternating Auxiliary Stack Automata.
In M. Nielsen and B. Rovan, editors, Proceedings of the 25th
Conference on Mathematical Foundations of Computer Science, number 1893 in
LNCS, pages 415425, Bratislava, Slovak Republic, August 2000. Springer.
We consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. In this way we get new characterizations of NP, the polynomial hierarchy, PSpace, and bounded query classes like NL^{NP[1]} and Θ_{2}P=P^{NP[O(logn)]}, in a uniform framework.

[22]  H. Bordihn and M. Holzer. On the Number of Active Symbols in L and CD Grammar Systems. In O. Boldt and H. Jürgensen, editors, PreProceedings of the Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Report No. 555, London, Ontario, Canada, July 2000. Department of Computer Science, The University of Western Onatario. 
[23] 
C. Damm, M. Holzer, and P. McKenzie.
The Complexity of Tensor Calculus.
In Proceedings of the 15th Annual IEEE Conference on
Computational Complexity, pages 7086, Florence, Italy, July 2000. IEEE
Computer Society Press.
DOI 
[24]  M. Holzer, K. Salomaa, and S. Yu. On the State Complexity of kEntry Deterministic Finite Automata. In O. Boldt and H. Jürgensen, editors, PreProceedings of the Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Report No. 555, London, Ontario, Canada, July 2000. Department of Computer Science, The University of Western Onatario. 
[25]  H. Fernau, M. Holzer, and R. Freund. Cooperating Distributed Grammar Systems with Exhausting Resources. In R. Freund and A. Kelemenova, editors, Proceedings of the International Workshop Grammar Systems, pages 113126, Bad Ischl, Austria, June 2000. Silesian University, Opava, Czech Republic. 
[26]  H. Bordihn and M. Holzer. Grammar Systems With Negated Conditions in Their Cooperation Protocols. In G. Rozenberg and W. Thomas, editors, Proceedings of the 4th International Conference Developments in Language Theory; Foundations, Applications, and Perspectives. World Scientific, 2000. 
[27]  M. Holzer. On fixed and general membership for external and internal contextual languages. In G. Rozenberg and W. Thomas, editors, Proceedings of the 4th International Conference Developments in Language Theory; Foundations, Applications, and Perspectives. World Scientific, 2000. 
[28]  H. Fernau, R. Freund, and M. Holzer. Regulated array grammars of finite index (Part I and II). In Gh. Paun and A. Salomaa, editors, Grammatical Models of MultiAgent Systems, volume 8 of Topics in Computer Mathematics, pages 157181,284296. Gordon and Breach, December 1998. 
[29]  H. Fernau, R. Freund, and M. Holzer. Character recognition with khead finite array automata. In Proceedings of the 7th International Workshop on Structural and Syntactic Pattern Recognition, number 1451 in LNCS, pages 282291, Sydney, Australia, August 1998. Springer. 
[30]  R. Freund, H. Fernau, and M. Holzer. Representations of recursively enumerable array languages by ddimensional contextual array grammars. In M. Margenstern, editor, MFCS'98 Satellite Workshop on Frontiers between Decidability and Undecidability, Brno, Czech Republic, August 1998. 
[31]  M. Holzer and M. Quenzer. VisA: Towards a Students' Green Card to Automata Theory and Formal Languages. In P. Strooper, editor, ACM Proceedings of the 3th Australasian Conference on Computer Science Education, pages 6775, The Univeristy of Queensland, Brisbane, Australia, July 1998. 
[32]  H. Fernau, R. Freund, and M. Holzer. The Generative Power of dDimensional #ContextFree Array Grammars. In M. Margenstern, editor, Proceedings of the 2nd International Colloquium Universal Machines and Computations, volume 2, pages 4356, IUT de Metz, Université de Metz, Metz, France, March 1998. 
[33] 
M. Holzer.
MultiHead Finite Automata: DataIndependent Versus
DataDependent Computations.
In I. Prívara and P. Ruzicka, editors, Proceedings of the
22nd Conference on Mathematical Foundations of Computer Science, number 1295
in LNCS, pages 299308, Bratislava, Slovakia, August 1997. Springer.
DOI We develop a framework on multihead finite automata that allows us to study the relation of parallel logarithmic time and sequential logarithmic space in a uniform and nonuniform setting in more detail. In both settings it turns out that NC1 requires dataindependent computationsâ€”the movement of the inputheads only depends on the length of the inputâ€”whereas logarithmic space is caught with data dependent computations on multihead finite state machines. This shed new light on the question whether these two classes coincide or not.

[34]  H. Fernau, M. Holzer, and R. Freund. Bounding resources in cooperating distributed grammar systems. In S. Bozapalidis, editor, Proceedings of the 3rd International Conference Developments in Language Theory, pages 261272, Aristotle University of Thessaloniki, Thessalomiki, Greece, July 1997. 
[35]  M. Holzer. On emptiness and counting for alternating finite automata. In J. Dassow, G. Rozenberg, and A. Salomaa, editors, Developments in Language Theory II; at the Crossroads of Mathematics, Computer Science and Biology, pages 8897. World Scientific, 1996. 
[36] 
C. Damm and M. Holzer.
Automata That Take Advice.
In J. Wiedermann and P. Hájek, editors, Proceedings of the
20th Conference on Mathematical Foundations of Computer Science, number 969
in LNCS, pages 149158, Prague, Czech Republic, August 1995. Springer.
DOI Karp and Lipton introduced advicetaking Turing machines to capture nonuniform complexity classes. We study this concept for automatalike models and compare it to other nonuniform models studied in connection with formal languages in the literature. Based on this we obtain complete separations of the classes of the Chomsky hierarchy relative to advices.

[37] 
C. Damm and M. Holzer.
Inductive Counting below LOGSPACE.
In I. Prívara and B. Rovan, editors, Proceedings of the 19th
Conference on Mathematical Foundations of Computer Science, number 841 in
LNCS, pages 276285, Kosice, Slovakia, August 1994. Springer.
DOI We apply the inductive counting technique to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too much. This shows that for an arbitrary space bound s(n), the class of languages accepted by nonuniform nondeterministic O(s(n)) space bounded Turing Machines is closed under complementation. As a consequence we obtain for arbitrary space bounds s(n) that the alternation hierarchy of nonuniform O(s(n)) space bounded Turing Machines collapses to its first level. This improves the previously known result of Immerman (1988) and Szelepcsényi (1988) to space bounds of order o(logn) in the nonuniform setting. This reveals a strong difference to the relations between the corresponding uniform complexity classes, since very recently it has been proved ...

[38]  C. Damm, M. Holzer, K.J. Lange, and P. Rossmanith. Deterministic 0L Languages Are of Very Low Complexity : D0L is in AC^{0}. In Developments in Language Theory, pages 305313. World Scientific, Singapore, 1994. 
[39] 
C. Damm, M. Holzer, and P. Rossmanith.
Expressing Uniformity via Oracles.
In Developments In Theoretical Computer Science, Proceedings of
the 7th International Meeting of Young Computer Scientists, pages 8392,
Smolonice Castle, Czechoslovakia, 1994. Gordon and Breach.
We study under what circumstances different uniformity notions for NC^{1} lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets which is proved in the paper: Auniform NC^{1}circuits are of the same computational power as DLOGTIMEuniform NC^{1}circuits with oracle access to tally sets in A. This characterization applies not only to classes A such as L or P but to all in some sense “wellbehaved” classes and especially to all standard complexity classes. We present many applications for this characterization: among them upward separations, depthuniformity tradeoffs, and inclusioncompleteness results for tally languages.

[40] 
M. Holzer and K.J. Lange.
On the Complexities of Linear LL(1) and LR(1) Grammars.
In Z. Ésik, editor, Proceedings of the 9th International
Conference on Fundamentals of Computation Theory, number 710 in LNCS, pages
299308, Szeged, Hungary, August 1993. Springer.
Several notions of deterministic linear languages are considered and compared with respect to their complexities and to the families of formal languages they generate. We exhibit close relationships between simple linear languages and the deterministic linear languages both according to Nasu and Honda and to Ibarra, Jiang, and Ravikumar. Deterministic linear languages turn out to be special cases of languages generated by linear grammars restricted to LL(1) conditions, which have a membership problem solvable in NC^{1}. In contrast to that, deterministic linear languages defined via automata models turn out to have a DSPACE(logn)complete membership problem. Moreover, they coincide with languages generated by linear grammars subject to LR(1) conditions.

[41] 
C. Damm, M. Holzer, and K.J. Lange.
The Parallel Complexity of Iterated Morphisms and the Arithmetic
of Small Numbers.
In I. M. Havel and V. Koubek, editors, Proceedings of the 17th
Conference on Mathematical Foundations of Computer Science, number 629 in
LNCS, pages 227235, Prague, Czechoslovakia, August 1992. Springer.
We improve several upper bounds to the complexity of the membership problem for languages defined by iterated morphisms (D0L systems). The complexity bounds are expressed in terms of DLOGTIMEuniform circuit families. We prove: 1) For polynomially growing D0L systems the membership problem is contained in AC^{0}. 2) For arbitrary D0L systems the membership problem is contained in NC^{1}. 3) The latter can be improved to TC^{0} if and only if upper bounds to a number of natural arithmetic problems can be improved to TC^{0}. 4) The general D0L membership problem (the D0L system is part of the input) is contained in Cook's class DET.

Technical Reports
[1]  M. Holzer and M. Kutrib. FlipPushdown Automata: Nondeterminism is Better Than Determinism. IFIG Research Report 0301, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, February 2003. 
[2]  M. Beaudry, J. M. Fernandez, and M. Holzer. A Common Algebraic Description for Probabilistic and Quantum Computations. Technical Report quantph/0212096, Los Alamos Preprint Archive, December 2002. 
[3]  M. Holzer and M. Kutrib. FlipPushdown Automata: k+1 Pushdown Reversals are Better Than k. IFIG Research Report 0206, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, November 2002. 
[4]  M. Holzer and M. Kutrib. Nondeterministic Descriptional Complexity of Regular Languages. IFIG Research Report 0205, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, September 2002. 
[5]  H. Bordihn, M. Holzer, and M. Kutrib. Economy of Description for Basic Constructions on Rational Transductions. IFIG Research Report 0204, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, July 2002. 
[6]  M.H. ter Beek, E. CsuhajVarjú, M. Holzer, and Gy. Vaszil. On Competence in Cooperating Distributed Grammar Systems. Technical Report 2002/1, Research Group on Modelling MultiAgent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary, 2002. 
[7]  M.H. ter Beek, E. CsuhajVarjú, M. Holzer, and Gy. Vaszil. On Competence in Cooperating Distributed Grammar Systems, Part II. Technical Report 2002/2, Research Group on Modelling MultiAgent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary, 2002. 
[8]  M.H. ter Beek, E. CsuhajVarjú, M. Holzer, and Gy. Vaszil. On Competence in Cooperating Distributed Grammar Systems, Part III. Technical Report 2002/3, Research Group on Modelling MultiAgent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary, 2002. 
[9]  M. Holzer and M. Kutrib. Unary Language Operations and Their Nondeterministic State Complexity. IFIG Research Report 0107, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, November 2001. 
[10]  H. Bordihn, J. Dassow, and M. Holzer. Extending Regular Expressions with Homomorphic Replacement. Technischer Bericht TUMI0102, Institut für Informatik, Technische Universität München, Arcisstraße 21, D80290 München, Germany, August 2001. 
[11]  M. Holzer and M. Kutrib. Improving Raster Image RunLength Encoding Using Data Order. IFIG Research Report 0105, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, July 2001. 
[12]  M. Holzer and St. Schwoon. Assembling Molecules in Atomix is Hard. Technischer Bericht TUMI0101, Institut für Informatik, Technische Universität München, Arcisstraße 21, D80290 München, Germany, May 2001. 
[13]  M. Holzer and M. Kutrib. State Complexity of Basic Operations on Nondeterministic Finite Automata. IFIG Research Report 0103, Institut für Informatik, JustusLiebigUniversität Gießen, Arndtstr. 2, D35392 Gießen, Germany, April 2001. 
[14]  M. Beaudry, M. Holzer, G. Niemann, and F. Otto. McNaughton Languages. Mathematische Schriften Kassel, PreprintReihe Fachbereich Mathematik/Informatik 26/00, Universität Gesamthochschule Kassel, November 2000. 
[15]  C. Damm, M. Holzer, and P. McKenzie. The Complexity of Tensor Calculus. Report TR00036, Electronic Colloquium on Computational Complexity (ECCC), June 2000. 
[16]  M. Holzer and W. Holzer. Tantrix^{TM} Rotation Puzzles are Intractable. Publication # 1164, Université de Montréal, Département d'informatique et de recherche opérationelle, C.P.6128, succ. Centreville, Montréal (Québec), H3C 3J7 Canada, October 1999. 
[17]  H. Bordihn and M. Holzer. Cooperating Distributed Grammar Systems with NonSuceeding Components. Publication # 1143, Université de Montréal, Département d'informatique et de recherche opérationelle, C.P.6128, succ. Centreville, Montréal (Québec), H3C 3J7 Canada, February 1999. 
[18]  H. Bordihn, H. Fernau, and M. Holzer. Accepting Pure Grammar Systems. Preprint Nr. 1, OttovonGuerickeUniversität Magdeburg, Fakultät für Informatik, Postfach 4120, D39016 Magdeburg, Germany, January 1999. 
[19]  H. Fernau and M. Holzer. Regulated Finite Index Language Families Collapse. Technical Report WSI9616, WilhelmSchickardInstitut für Informatik, Universität Tübingen, Sand 13, D72076 Tübingen, Germany, May 1996. 
[20]  H. Fernau and M. Holzer. Bidirectional cooperation distributed grammar systems. Technical Report WSI9601, WilhelmSchickardInstitut für Informatik, Universität Tübingen, Sand 13, D72076 Tübingen, Germany, February 1996. 
[21]  H. Fernau, R. Freund, and M. Holzer. External versus internal hybridization in cooperating distributed grammar systems. Technical Report TR 1852/FR1/96, Institut für Computersprachen, Technische Universität Wien, Resselgasse 3, A1040 Wien, Austria, January 1996. 
[22]  L. Kászonyi and M. Holzer. On the Generalized FlipFlop Lemma. Technical Report WSI9617, WilhelmSchickardInstitut für Informatik, Universität Tübingen, Sand 13, D72076 Tübingen, Germany, 1996. 
[23]  C. Damm and M. Holzer. Automata That Take Advice. Technical Report WSI9514, WilhelmSchickardInstitut für Informatik, Universität Tübingen, Sand 13, D72076 Tübingen, Germany, November 1995. 
[24]  C. Damm, M. Holzer, and P. Rossmanith. Expressing uniformity via oracles. Technical Report 9501, Universiät Trier, Fachbereich IV  Mathematik/Informatik, Universität Trier, D54286 Trier, Germany, January 1995. 
[25]  C. Damm and M. Holzer. Inductive Counting below LOGSPACE. Technical Report 9412, Universiät Trier, Fachbereich IV  Mathematik/Informatik, Universität Trier, D54286 Trier, Germany, October 1994. 
Parts of this pages were generated by bibtex2thml.