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. TantrixTM Rotation Puzzles are Intractable. Discrete Applied Mathematics, 144(3):345-358, December 2004.
DOI
It is shown that the Tantrix rotation puzzle can be used to emulate a circuit with AND- and NOT-gates. 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., NP-complete. 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):319-347, November 2004.
DOI
We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of n-state (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 nn(1-(2)/(sqrt(n))) for the size of the syntactic monoid of a language accepted by an n-state 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 non-bijective mapping merging elements from these two cycles. As a by-product 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 non-bijective mapping.

[3] M. Holzer and St. Schwoon. Assembling Molecules in Atomix is Hard. Theoretical Computer Science, 313(3):447-462, 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 non-emptiness intersection problem for finite automata is solvable. This shows that the game under consideration is PSPACE-complete, 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):175-188, 2004.
[5] M. Holzer and M. Kutrib. Nondeterministic Descriptional Complexity of Regular Languages. International Journal of Foundations of Computer Science, 14(6):1087-1102, 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 operations-concatenation, iteration, λ-free iteration-and 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(1-3):307-326, 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:1581-1628, 2003.
DOI
In 1988 the Church-Rosser languages were introduced by McNaughton et al. as those languages that are recognized by finite, length-reducing and confluent string-rewriting systems using extra non-terminal symbols. Here we generalize this concept by considering classes of languages that are obtained by other types of string-rewriting 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 phrase-structure grammar. We investigate the relationships between the various McNaughton families, obtaining an extensive hierarchy of classes that includes many well-known language and complexity classes as well as some new classes. Further, we consider some closure and non-closure properties for those McNaughton families that are contained in the class of context-free 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):54-89, January 2003.
DOI
[9] H. Fernau, R. Freund, and M. Holzer. Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes <=k and =k. Theoretical Computer Science, 299(1-3):633-662, 2003.
[10] H. Bordihn, H. Fernau, and M. Holzer. Accepting Pure Grammars. Publicationes Mathematicae Debrecen, 60(Supplementum):483-510, 2002.
[11] M. Holzer. Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations. Theoretical Computer Science, 286:97-116, 2002.
DOI
We develop a multi-head 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 data-independent or oblivious computations, i.e., the movement of the input-heads only depends on the length of the input, whereas logarithmic space is captured with data-dependent computations on multi-head 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(1-2):405-426, 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):411-426, 2001.
[14] M. Holzer, K. Salomaa, and S. Yu. On the State Complexity of k-Entry Deterministic Finite Automata. Journal of Automata, Languages and Combinatorics, 6(4):453-466, 2001.
[15] H. Bordihn and M. Holzer. Grammar Systems with Negated Conditions in Their Cooperation Protocols. Journal of Universal Computer Science, 6(12):1165-1184, 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 t-mode of derivation, where such non-t-components 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 non-t-components turn out to give new characterizations of the class of programmed context-free languages or recurrent programmed context-free 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:365-375, 1999.
[17] H. Bordihn and M. Holzer. On a hierarchy of languages generated by cooperating distributed grammar systems. Information Processing Letters, 69(2):59-62, January 1999.
DOI
For cooperating distributed grammar systems working in = k-mode 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):787-806, 1998.
[19] C. Damm, M. Holzer, and P. Rossmanith. Expressing Uniformity via Oracles. Theory of Computing Systems, 30(4):355-366, 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: A-uniform circuits of logarithmic depth are of the same computational power as DLOGTIME-uniform 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 “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages.

[20] M. Holzer and P. Rossmanith. A simpler grammar for Fibonacci Numbers. The Fibonacci Quarterly, 34(5):465-466, November 1996.
[21] C. Damm and M. Holzer. Inductive Counting for Width-Restricted Branching Programs. Information and Computation, 130(1):91-99, October 1996.
DOI
As an application of the inductive counting technique to a circuit-like 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 Multi-Agent Systems: The Case of Cooperating Distributed Grammar Systems. Journal of Computers and Artificial Intelligence, 15(2):123-139, 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 context-sensitive languages by accepting CD grammar systems (with or without λ-productions) working in t-mode. Moreover, accepting hybrid CD (HCD) grammar systems with λ-productions characterize the recursively enumerable languages.

[23] H. Fernau and M. Holzer. Accepting Multi-Agent Systems II. Acta Cybernetica-Selected Papers of the Workshop Grammars Systems: Recent Results and Perspectives, Budapest, July 1996, 12(4):361-379, 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:139-155, June 2004.
[2] M. Holzer. Computational Complexity. In C. Martín-Vide and V. Mitrana, editors, Formal Languages and Applications, number 148 in Studies in Fuzziness and Soft Computing, pages 227-247. Springer, 2004.
[3] M. Holzer (editor). Workshop `{P}etrinetze' und 13. GI Theorietag `{A}utomaten und {F}ormale {S}prachen'. Technical Report TUM-I0322, Institut für Informatik, Technische Universität München, Boltzmannstraße 3, D-85748 Garching bei München, Germany, December 2003.
[4] M. Holzer. Aspects on the Descriptional Complexity of Finite Automata. In E. Csuhaj-Varjú, Ch. Kintala, D. Wotschke, and Gy. Vaszil, editors, Proceedings of the 5th International Workshop on Descriptional Complexity of Formal Systems, pages 26-41, Budapest, Hungary, July 2003. MTA SZTAKI.
[5] W. Brauer, M. Holzer, B. König, and S. Schwoon. The Theory of Finite-State Adventures. Bulletin of the European Association for Theoretical Computer Science, 79:230-237, February 2003.
[6] H. Bordihn, H. Fernau, and M. Holzer. On Iterated Sequential Transducer. In C. Martin-Vide and V. Mitrana, editors, Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back, pages 121-130. Taylor and Francis, London, 2003.
[7] M. Holzer and P. McKenzie. On Auxiliary Pushdown and Stack Automata. SIGACT News, 33(1):32-35, March 2002.
[8] H. Bordihn and M. Holzer. On the Computational Complexity of Synchronized Context-Free Languages. Journal of Universal Computer Science, 8(2):119-140, 2002.
PDF  PS
[9] H. Fernau and M. Holzer. External Contextual and Conditional Languages. In C. Martin-Vide and Gh. Paun, editors, Recent Topics in Mathematical and Computational Linguistics, pages 104-120. Romanian Academy, Bucharest, June 2000.
[10] M. Holzer. Data-Independent Versus Data-Dependent Computations on Multi-Head Automata. Number 10 in Edition VERSAL. Bertz, December 1998.
[11] H. Fernau and M. Holzer. Conditional Context-Free 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 10-26. 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 440-453. Springer, 1997.
[13] M. Holzer (editor). 4. GI Theorietag `{A}utomaten und {F}ormale {S}prachen'. Technical Report WSI-95-10, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, May 1995.

Conferences

[1] M. H. ter Beek, E. Csuhaj-Varjú, 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 76-88, 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 = k-competent (<=k-, >=k-competent, 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 (context-free) 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 Automata-A 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 102-113, Auckland, New Zealand, December 2004. Springer.
DOI
Input-reversal 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 context-free indexed languages, and that k + 1 input reversals are better than k for both deterministic and nondeterministic input-reversal pushdown automata, i.e., there are languages which can be recognized by a deterministic input-reversal pushdown automaton with k + 1 input reversals but which cannot be recognized with k input reversals (deterministic or nondeterministic). In passing, input-reversal finite automata are investigated. Moreover, an inherent relation between input-reversal pushdown automata and controlled linear context-free languages are shown, leading to an alternative description of Khabbaz geometric hierarchy of languages by input-reversal 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 GOTO-Programs. In M. Margenstern, editor, Proceedings of the 4th International Conference Machines, Computations and Universality, number 3354 in LNCS, pages 233-244, St. Petersburg, Russia, September 2004. Springer.
DOI
We study the register complexity of LOOP-, WHILE-, and GOTO-programs, that is the number of registers (or variables) needed to compute certain unary (partial) functions from the non-negative integers to the non-negative integers. It turns out that the hierarchy of LOOP-computable (WHILE-, and GOTO-computable, respectively) functions f:N0->N0 (partial functions f:N0->N0, 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 GOTO-programs 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 851-862, 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 sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa. 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 Non-Semi-Decidability Problems for Linear and Deterministic Context-Free 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 68-79, Queen's University, Kingston, Ontario, Canada, July 2004. Springer.
DOI
We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semi-decidability for all of the aforementioned operations, if the underlying alphabet contains at least two letters. The non-semi-decidability 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. Csuhaj-Varjú and Gy. Vaszil, editors, Preliminary Proceedings of Grammar Systems Week, pages 66-82, Budapest, Hungary, July 2004. MTA SZTAKI.
[7] E. D. Demaine, M. Hoffmann, and M. Holzer. PushPush-k is PSPACE-Complete. In P. Ferragnia and R. Grossi, editors, Proceedings of the 3rd International Conference on FUN with Algorithms, pages 159-170, Island of Elba, Italy, May 2004. Edizioni Plus, Universitá di Pisa.
[8] M. Holzer, A. Klein, and M. Kutrib. On the NP-Completeness 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 77-89, Island of Elba, Italy, May 2004. Edizioni Plus, Universitá di Pisa.
[9] M. Holzer St. Schwoon. Reflections on Reflexion-Computational Complexity Considerations on a Puzzle Game. In P. Ferragnia and R. Grossi, editors, Proceedings of the 3rd International Conference on FUN with Algorithms, pages 90-105, 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 349-360, Szeged, Hungary, July 2003. Springer.
[11] M. Holzer and M. Kutrib. Flip-Pushdown 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 361-372, 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 148-157, Tours, France, July 2003. Springer.
[13] M. Holzer and M. Kutrib. Flip-Pushdown 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 490-501, Eindhoven, The Netherlands, June-July 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 258-269, 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 162-172, 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 173-185, 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 non-zero 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 340-348, Wien, Austria, July 2001. Springer.
[18] H. Fernau and M. Holzer. Graph-Controlled 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 79-90, Wien, Austria, July 2001. Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg.
[19] M. Holzer and M. Kutrib. Improving raster image run-length 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 161-176, Pretoria, South Africa, July 2001. Springer.
[20] M. Holzer and W. Holzer. TantrixTM Rotation Puzzles are Intractable. In Proceedings of the 2nd International Conference FUN with Algorithms 2, pages 165-182, 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 NOT-gates. 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., NP-complete. 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 415-425, 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 NLNP[1] and Θ2P=PNP[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, Pre-Proceedings 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 70-86, Florence, Italy, July 2000. IEEE Computer Society Press.
DOI
[24] M. Holzer, K. Salomaa, and S. Yu. On the State Complexity of k-Entry Deterministic Finite Automata. In O. Boldt and H. Jürgensen, editors, Pre-Proceedings 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 113-126, 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 Multi-Agent Systems, volume 8 of Topics in Computer Mathematics, pages 157-181,284-296. Gordon and Breach, December 1998.
[29] H. Fernau, R. Freund, and M. Holzer. Character recognition with k-head finite array automata. In Proceedings of the 7th International Workshop on Structural and Syntactic Pattern Recognition, number 1451 in LNCS, pages 282-291, Sydney, Australia, August 1998. Springer.
[30] R. Freund, H. Fernau, and M. Holzer. Representations of recursively enumerable array languages by d-dimensional 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 67-75, The Univeristy of Queensland, Brisbane, Australia, July 1998.
[32] H. Fernau, R. Freund, and M. Holzer. The Generative Power of d-Dimensional #-Context-Free Array Grammars. In M. Margenstern, editor, Proceedings of the 2nd International Colloquium Universal Machines and Computations, volume 2, pages 43-56, IUT de Metz, Université de Metz, Metz, France, March 1998.
[33] M. Holzer. Multi-Head Finite Automata: Data-Independent Versus Data-Dependent 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 299-308, Bratislava, Slovakia, August 1997. Springer.
DOI
We develop a framework on multi-head 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 data-independent computations—the movement of the input-heads only depends on the length of the input—whereas logarithmic space is caught with data dependent computations on multi-head 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 261-272, 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 88-97. 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 149-158, Prague, Czech Republic, August 1995. Springer.
DOI
Karp and Lipton introduced advice-taking Turing machines to capture nonuniform complexity classes. We study this concept for automata-like 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 276-285, 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 AC0. In Developments in Language Theory, pages 305-313. 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 83-92, Smolonice Castle, Czechoslovakia, 1994. Gordon and Breach.
We study under what circumstances different uniformity notions for NC1 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: A-uniform NC1-circuits are of the same computational power as DLOGTIME-uniform NC1-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 “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization: among them upward separations, depth-uniformity trade-offs, and inclusion-completeness 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 299-308, 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 NC1. 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 227-235, 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 DLOGTIME-uniform circuit families. We prove: 1) For polynomially growing D0L systems the membership problem is contained in AC0. 2) For arbitrary D0L systems the membership problem is contained in NC1. 3) The latter can be improved to TC0 if and only if upper bounds to a number of natural arithmetic problems can be improved to TC0. 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. Flip-Pushdown Automata: Nondeterminism is Better Than Determinism. IFIG Research Report 0301, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 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 quant-ph/0212096, Los Alamos Preprint Archive, December 2002.
[3] M. Holzer and M. Kutrib. Flip-Pushdown Automata: k+1 Pushdown Reversals are Better Than k. IFIG Research Report 0206, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 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, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 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, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, July 2002.
[6] M.H. ter Beek, E. Csuhaj-Varjú, M. Holzer, and Gy. Vaszil. On Competence in Cooperating Distributed Grammar Systems. Technical Report 2002/1, Research Group on Modelling Multi-Agent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary, 2002.
[7] M.H. ter Beek, E. Csuhaj-Varjú, M. Holzer, and Gy. Vaszil. On Competence in Cooperating Distributed Grammar Systems, Part II. Technical Report 2002/2, Research Group on Modelling Multi-Agent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary, 2002.
[8] M.H. ter Beek, E. Csuhaj-Varjú, M. Holzer, and Gy. Vaszil. On Competence in Cooperating Distributed Grammar Systems, Part III. Technical Report 2002/3, Research Group on Modelling Multi-Agent 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, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, November 2001.
[10] H. Bordihn, J. Dassow, and M. Holzer. Extending Regular Expressions with Homomorphic Replacement. Technischer Bericht TUM-I0102, Institut für Informatik, Technische Universität München, Arcisstraße 21, D-80290 München, Germany, August 2001.
[11] M. Holzer and M. Kutrib. Improving Raster Image Run-Length Encoding Using Data Order. IFIG Research Report 0105, Institut für Informatik, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, July 2001.
[12] M. Holzer and St. Schwoon. Assembling Molecules in Atomix is Hard. Technischer Bericht TUM-I0101, Institut für Informatik, Technische Universität München, Arcisstraße 21, D-80290 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, Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen, Germany, April 2001.
[14] M. Beaudry, M. Holzer, G. Niemann, and F. Otto. McNaughton Languages. Mathematische Schriften Kassel, Preprint-Reihe 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 TR00-036, Electronic Colloquium on Computational Complexity (ECCC), June 2000.
[16] M. Holzer and W. Holzer. TantrixTM Rotation Puzzles are Intractable. Publication # 1164, Université de Montréal, Département d'informatique et de recherche opérationelle, C.P.6128, succ. Centre-ville, Montréal (Québec), H3C 3J7 Canada, October 1999.
[17] H. Bordihn and M. Holzer. Cooperating Distributed Grammar Systems with Non-Suceeding Components. Publication # 1143, Université de Montréal, Département d'informatique et de recherche opérationelle, C.P.6128, succ. Centre-ville, Montréal (Québec), H3C 3J7 Canada, February 1999.
[18] H. Bordihn, H. Fernau, and M. Holzer. Accepting Pure Grammar Systems. Preprint Nr. 1, Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, Postfach 4120, D-39016 Magdeburg, Germany, January 1999.
[19] H. Fernau and M. Holzer. Regulated Finite Index Language Families Collapse. Technical Report WSI-96-16, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, May 1996.
[20] H. Fernau and M. Holzer. Bidirectional cooperation distributed grammar systems. Technical Report WSI-96-01, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 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 185-2/FR-1/96, Institut für Computersprachen, Technische Universität Wien, Resselgasse 3, A-1040 Wien, Austria, January 1996.
[22] L. Kászonyi and M. Holzer. On the Generalized Flip-Flop Lemma. Technical Report WSI-96-17, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, 1996.
[23] C. Damm and M. Holzer. Automata That Take Advice. Technical Report WSI-95-14, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, November 1995.
[24] C. Damm, M. Holzer, and P. Rossmanith. Expressing uniformity via oracles. Technical Report 95-01, Universiät Trier, Fachbereich IV - Mathematik/Informatik, Universität Trier, D-54286 Trier, Germany, January 1995.
[25] C. Damm and M. Holzer. Inductive Counting below LOGSPACE. Technical Report 94-12, Universiät Trier, Fachbereich IV - Mathematik/Informatik, Universität Trier, D-54286 Trier, Germany, October 1994.

Parts of this pages were generated by bibtex2thml.