Publications
These selected publications (since 2005) are listed in reverse chronological order. Copies of papers will be provided upon request. Publications before 2005 can be found here.
Journal Articles
| [1] |
H. Bordihn, J. Dassow, and M. Holzer.
Extending Regular Expressions With Homomorphic Replacement.
RAIRO-Informatique théorique et Applications / Theoretical
Informatics and Applications, 2010.
Accepted for publication.
Abstract |
| [2] |
S. Bensch, H. Bordihn, M. Holzer, and M. Kutrib.
On Input-Revolving Deterministic and Nondeterministic Finite
Automata.
Information and Computation, 207(11):1140-1155, November 2009.
DOI Abstract |
| [3] |
F. Biegler, M. Daley, M. Holzer, and I. McQuillan.
On the Uniqueness and Decomposition of Shuffle on Two Words.
Theoretical Computer Science, 410(38-40):3711-3724, September
2009.
DOI Abstract |
| [4] |
H. Gruber and M. Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
Theoretical Computer Science, 410(35):3281-3289, August 2009.
DOI Abstract |
| [5] |
H. Bordihn, M. Holzer, and M. Kutrib.
Determinization of Finite Automata Accepting Subregular
Languages.
Theoretical Computer Science, 410(35):3209-3222, August 2009.
DOI Abstract |
| [6] |
F. Brandt, F. Fischer, and M. Holzer.
Symmetries and the Complexity of Pure Nash Equilibrium.
Journal of Computer and System Sciences, 75(3):163-177, May
2009.
DOI Abstract |
| [7] |
H. Gruber, M. Holzer, and M. Kutrib.
More on the Size of Higman-Haines Sets: Effective
Construction.
Fundamenta Informaticae, 91(1):105-121, 2009.
DOI Abstract |
| [8] |
M. Holzer and M. Kutrib.
Nondeterministic Finite Automata-Recent Results on the
Descriptional and Computational Complexity.
International Journal of Foundations of Computer Science,
20(4):563-580, 2009.
DOI Abstract |
| [9] |
H. Bordihn and M. Holzer.
A Note on Cooperating Distributed Grammar Systems Working in
Combined Modes.
Information Processing Letters, 108(1):10-14, September 2008.
DOI Abstract |
| [10] |
H. Gruber and M. Holzer.
Results on the Average State and Transition Complexity of Finite
Automata Accepting Finite Languages.
Theoretical Computer Science, 387(2):155-166, November 2007.
DOI Abstract |
| [11] |
H. Gruber, M. Holzer, and M. Kutrib.
The size of Higman-Haines Sets.
Theoretical Computer Science, 387(2):167-176, November 2007.
DOI Abstract |
| [12] |
H. Bordihn, M. Holzer, and M. Kutrib.
Hybrid Extended Finite Automata.
International Journal of Foundations of Computer Science,
18(4):745-760, August 2007.
DOI Abstract |
| [13] |
M. Beaudry and M. Holzer.
The Complexity of Tensor Circuit Evaluation.
Computational Complexity, 16(1):60-111, May 2007.
DOI Abstract |
| [14] |
H. Bordihn and M. Holzer.
Cooperating Distributed Grammar Systems as Models of Distributed
Problem Solving, Revisited.
Fundamenta Informaticae, 76(3):255-270, March 2007.
Abstract |
| [15] |
M. Holzer, M. Kutrib, and J. Reimann.
Non-Recursive Trade-Offs for Deterministic Restarting Automata.
Journal of Automata, Languages and Combinatorics,
12(1/2):195-213, 2007.
Abstract |
| [16] |
H. Bordihn, H. Fernau, M. Holzer, V. Manca, and C. Martin-Vide.
Iterated sequential transducers as languages generating
devices.
Theoretical Computer Science, 369(1-3):67-81, December 2006.
DOI Abstract |
| [17] |
H. Bordihn and M. Holzer.
Programmed Grammars and Their Relation to the LBA Problem.
Acta Informatica, 43(4):223-242, November 2006.
DOI Abstract |
| [18] |
F. Fischer, M. Holzer, and S. Katzenbeisser.
The influence of neighbourhood and choice on the complexity of
finding pure Nash equilibria.
Information Processing Letters, 99(6):239-245, September 2006.
DOI |
| [19] |
E. Csuhaj-Varjú, J. Dassow, and M. Holzer.
CD Grammar Systems with Competence Based Entry Conditions in
Their Cooperation Protocols.
International Journal of Computer Mathematics, 83(2):159-169,
February 2006.
DOI Abstract |
| [20] |
M. Holzer and M. Kutrib.
Variable Complexity of Simple Programs.
Fundamenta Informaticae, 74(4):1-18, 2006.
Abstract |
| [21] |
M. Beaudry, J. M. Fernandez, and M. Holzer.
A Common Algebraic Description of Probabilistic and Quantum
Computations.
Theoretical Computer Science, 345(2/3):206-234, November 2005.
DOI Abstract |
| [22] |
J. Dassow and M. Holzer.
Language Families Defined by a Ciliate Bio-Operation:
Hierarchies and Decision Problems.
International Journal of Foundations of Computer Science,
16(4):645-662, August 2005.
DOI Abstract |
| [23] |
H. Bordihn, M. Holzer, and M. Kutrib.
Unsolvability Levels of Operation Problems for Subclasses of
Context-Free Languages.
International Journal of Foundations of Computer Science,
16(3):423-440, June 2005.
DOI Abstract |
| [24] |
M. Holzer and M. Kutrib.
On the Descriptional Complexity of Finite Automata with Modified
Acceptance Conditions.
Theoretical Computer Science, 330(2):267-285, February 2005.
DOI Abstract |
Books and Invited Papers
| [1] | H. Bordihn, R. Freund, M. Holzer, M. Kutrib, and F. Otto. Workshop on Non-Classical Models for Automata and Applications (NCMA). Österreichische Computer Gesellschaft, Vienna, Austria, September 2009. |
| [2] |
M. Holzer and M. Kutrib.
Descriptional and Computational Complexity of Finite Automata.
In A. H. Dediu, A. M. Ionescu, and C. Martín-Vide, editors,
Proceedings of the 3rd International Conference Language and Automata
Theory and Applications, number 5457 in LNCS, pages 23-42, Tarragona,
Spain, April 2009. Springer.
DOI |
| [3] |
M. Holzer, M. Kutrib, and A. Malcher (editors).
18. Theorietag Automaten und Formale Sprachen.
Technical report, Institut für Informatik,
Justus-Liebig-Universität Giessen, Arndtstraße 2, D-35392 Giessen,
Germany, September 2008.
|
| [4] |
M. Holzer and M. Kutrib.
Nondeterministic Finite Automata-Recent Results on the
Descriptional and Computational Complexity.
In O. H. Ibarra and B. Ravikumar, editors, Proceedings of the
13th Conference on Implementation and Application of Automata, number 5148
in LNCS, pages 1-16, San Francisco, California, July 2008. Springer.
DOI |
| [5] |
M. H. ter Beek, E. Csuhaj-Varjú, Gy. Vaszil, and M. Holzer.
On Competence in CD Grammar Systems with Parallel Rewriting.
International Journal of Foundations of Computer Science,
18(6):1425-1439, December 2007.
DOI |
| [6] | H. Fernau, R. Freund, and M. Holzer. Representations of Recursively Enumerable Array Languages by Contextual Array Grammars. Fundamenta Informaticae, 64(1-4):159-170, February 2005. |
Conferences
| [1] |
F. Brandt, F. Fischer, and M. Holzer.
On Iterated Dominance, Matrix Elimination, and Matched Paths.
In J.-Y. Marion and T. Schwentick, editors, Proceedings of the
27th International Symposium on Theoretical Aspects of Computer Science,
Nancy, France, February 2010.
Accepted for publication.
Abstract |
| [2] |
M. Holzer and A. Maletti.
An n logn Algorithm for Hyper-Minimizing States in a
(Minimized) Deterministic Automaton.
In S. Maneth, editor, Proceedings of the 14th Conference on
Implementation and Application of Automata, number 5642 in LNCS, pages
4-13, Sydney, Australia, July 2009. Springer.
DOI Abstract |
| [3] |
H. Gruber, M. Holzer, and M. Tautschnig.
Short Regular Expressions from Finite Automata: Empirical
Results.
In S. Maneth, editor, Proceedings of the 14th Conference on
Implementation and Application of Automata, number 5642 in LNCS, pages
188-197, Sydney, Australia, July 2009. Springer.
DOI Abstract |
| [4] |
H. Gruber, M. Holzer, and M. Kutrib.
On Measuring Non-Recursive Trade-Offs.
In J. Dassow, G. Pighizzini, and B. Truthe, editors, Proceedings
of the 11th Workshop on Descriptional Complexity of Formal Systems, pages
187-198, Fakultät für Informatik, Postfach 4120, D-39016 Magdeburg,
Germany, July 2009. Otto-von-Guericke-Universität Magdeburg.
Abstract |
| [5] |
H. Gruber and M. Holzer.
Tight Bounds on the Descriptional Complexity of Regular
Expressions.
In V. Diekert and D. Nowotka, editors, Proceedings of the 13th
International Conference Developments in Language Theory, number 5583 in
LNCS, pages 276-287, Stuttgart, Germany, June-July 2009. Springer.
DOI Abstract |
| [6] |
H. Bordihn, M. Holzer, and M. Kutrib.
Undecidability of Operation Problems for T0L Languages and
Subclasses.
In A. H. Dediu, A. M. Ionescu, and C. Martín-Vide, editors,
Proceedings of the 3rd International Conference Language and Automata
Theory and Applications, number 5457 in LNCS, pages 236-246, Tarragona,
Spain, April 2009. Springer.
DOI Abstract |
| [7] |
F. Brandt, F. Fischer, and M. Holzer.
Equilibria of Graphical Games with Symmetries (Extended
Abstract).
In C. Papadimitriou and S. Zhang, editors, Proceedings of the
4th Workshop on Internet & Network Economic, number 5385 in LNCS, pages
198-209, Shanghai, China, December 2008. Springer.
DOI Abstract |
| [8] |
M. Holzer, M. Kutrib, and A. Malcher.
Multi-Head Finite Automata: Characterizations, Concepts and Open
Problems.
In T. Neary, D. Woods, A. K. Seda, and N. Murphy, editors,
Proceedings of the Workshop on The Complexity of Simple Programs, pages
117-136, Cork, Ireland, December 2008. Cork University Press.
Abstract |
| [9] |
H. Gruber and M. Holzer.
Provably Shorter Regular Expressions from Deterministic Finite
Automata (Extended Abstract).
In M. Ito and M. Toyama, editors, Proceedings of the 12th
International Conference Developments in Language Theory, number 5257 in
LNCS, pages 383-395, Kyoto, Japan, September 2008. Springer.
DOI Abstract |
| [10] |
H. Gruber and M. Holzer.
Finite Automata, Digraph Connectivity, and Regular Expression
Size.
In L. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldórsson,
A. Ingólfsdóttir, and I. Walkuwiewicz, editors, Proceedings of
the 35th International Colloqium on Automata, Languages and Propgramming,
number 5126 in LNCS, pages 39-50, Reykjavik, Iceland, July 2008. Springer.
DOI Abstract |
| [11] |
H. Bordihn, M. Holzer, and M. Kutrib.
State Complexity of NFA to DFA Conversion for Subregular
Language Families.
In C. Câmpeanu and G. Pighizzini, editors, Proceedings of
the 10th Workshop on Descriptional Complexity of Formal Systems, pages
85-96, Charlottetown, Prince Edward Island, Canada, July 2008. University of
Prince Edward Island, Departement of Computer Science and Information
Technology.
Abstract |
| [12] |
H. Gruber and M. Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
In C. Câmpeanu and G. Pighizzini, editors, Proceedings of
the 10th Workshop on Descriptional Complexity of Formal Systems, pages
182-193, Charlottetown, Prince Edward Island, Canada, July 2008. University
of Prince Edward Island, Departement of Computer Science and Information
Technology.
Abstract |
| [13] |
S. Bensch, H. Bordihn, M. Holzer, and M. Kutrib.
Deterministic Input-Reversal and Input-Revolving Finite
Automata.
In C. Martín-Vide, F. Otto, and H. Fernau, editors,
Proceedings of the 2nd International Conference Language and Automata
Theory and Applications, number 5196 in LNCS, pages 113-124, Tarragona,
Spain, March 2008. Springer.
DOI Abstract |
| [14] |
H. Bordihn and M. Holzer.
Random Context in Regulated Rewriting Versus Cooperating
Distributed Grammar Systems.
In C. Martín-Vide, F. Otto, and H. Fernau, editors,
Proceedings of the 2nd International Conference Language and Automata
Theory and Applications, number 5196 in LNCS, pages 125-136, Tarragona,
Spain, March 2008. Springer.
DOI Abstract |
| [15] |
H. Gruber, M. Holzer, and M. Kutrib.
More on the Size of Higman-Haines Sets: Effective
Constructions.
In J. O. Durand-Lose and M. Margenstern, editors, Proceedings of
the 5th International Conference Machines, Computations, and Universality,
number 4664 in LNCS, pages 193-204, Orléans, France, September 2007.
Springer.
DOI Abstract |
| [16] |
H. Bordihn, M. Holzer, and M. Kutrib.
Hairpin Finite Automata.
In T. Harju, J. Karhumäki, and A. Lepistö, editors,
Proceedings of the 11th International Conference Developments in Language
Theory, number 4588 in LNCS, pages 108-119, Turku, Finland, July 2007.
Springer.
DOI Abstract |
| [17] |
H. Gruber and M. Holzer.
Inapproximability of Nondeterministic State and Transition
Complexity Assuming P<>NP.
In T. Harju, J. Karhumäki, and A. Lepistö, editors,
Proceedings of the 11th International Conference Developments in Language
Theory, number 4588 in LNCS, pages 205-216, Turku, Finland, July 2007.
Springer.
DOI Abstract |
| [18] |
H. Gruber, M. Holzer, and O. Ruepp.
Sorting the Slow Way: An Analysis of Perversely Awful Randomized
Sorting Algorithms.
In P. Crescenzi, G. Prencipe, and G. Pucci, editors, Proceedings
of the 4th International Conference on FUN with Algorithms, number 4475
in LNCS, pages 183-197, Castiglioncello, Italy, June 2007. Springer.
DOI Abstract |
| [19] |
M. Holzer and O. Ruepp.
The Troubles of Interior Design-A Complexity Analysis of the
Game Heyawake.
In P. Crescenzi, G. Prencipe, and G. Pucci, editors, Proceedings
of the 4th International Conference on FUN with Algorithms, number 4475
in LNCS, pages 198-212, Castiglioncello, Italy, June 2007. Springer.
DOI Abstract |
| [20] |
H. Gruber and M. Holzer.
Computational Complexity of NFA Minimization for Finite and
Unary Languages.
In Preproceedings of the 1st International Conference on
Language and Automata Theory and Applications, Technical Report 35/07, pages
261-272, Tarragona, Spain, March 2007. Research Group on Mathematical
Linguistics, Universitat Rovira i Virgili.
Abstract |
| [21] |
F. Brandt, F. Fischer, and M. Holzer.
Symmetries and the Complexity of Pure Nash Equilibrium.
In W. Thomas and P. Weil, editors, Proceedings of the 24th
International Symposium on Theoretical Aspects of Computer Science, number
4393 in LNCS, pages 212-223, Aachen, Germany, February 2007. Springer.
DOI Abstract |
| [22] |
H. Bordihn, M. Holzer, and M. Kutrib.
Hybrid Extended Finite Automata.
In O. H. Ibarra and H.-C. Yen, editors, Proceedings of the
11th International Conference on Implementation and Application of
Automata, number 4094 in LNCS, pages 34-45, Taipei, Taiwan, August 2006.
Springer.
DOI Abstract |
| [23] |
H. Gruber and M. Holzer.
Finding Lower Bounds for Nondeterministic State Complexity is
Hard (Extended Abstract).
In O. H. Ibarra and Z. Dang, editors, Proceedings of the 10th
International Conference on Developments in Language Theory, number 4036 in
LNCS, pages 363-374, Santa Barbara, California, USA, June 2006. Springer.
DOI Abstract |
| [24] |
M. Holzer and M. Kutrib.
The size of Higman-Haines sets.
In H. Leung and G. Pighizzini, editors, Proceedings of the 8th
Workshop on Descriptional Complexity of Formal Systems, pages 177-187, Las
Cruces, New Mexico, USA, June 2006.
Computer Science Technical Report NMSU-CS-2006-001.
Abstract |
| [25] |
H. Gruber and M. Holzer.
Results on the average state and transition complexity of finite
automata.
In H. Leung and G. Pighizzini, editors, Proceedings of the 8th
Workshop on Descriptional Complexity of Formal Systems, pages 267-275, Las
Cruces, New Mexico, USA, June 2006.
Computer Science Technical Report NMSU-CS-2006-001.
Abstract |
| [26] |
M. Holzer and F. Otto.
Shrinking Multi-Pushdown Automata.
In M. Liskiewicz and R. Reischuk, editors, Proceedings of
the 15th International Conference on Fundamentals of Computation Theory,
number 3623 in LNCS, pages 305-316, Lübeck, Germany, August 2005.
Springer.
DOI Abstract |
| [27] |
H. Bordihn, M. Holzer, and M. Kutrib.
Revolving-Input Finite Automata.
In C. De Felice and A. Restivo, editors, Proceedings of the
9th International Conference on Developments in Language Theory, number
3572 in LNCS, pages 168-179, Palermo, Italy, July 2005. Springer.
DOI Abstract |
| [28] |
H. Gruber, M. Holzer, M. Kiehn, and B. König.
On Timed Automata with Discrete Time-Structural and Language
Theoretical Characterization.
In C. De Felice and A. Restivo, editors, Proceedings of the
9th International Conference on Developments in Language Theory, number
3572 in LNCS, pages 272-283, Palermo, Italy, July 2005. Springer.
DOI Abstract |
| [29] |
M. Holzer, M. Kutrib, and J. Reimann.
Descriptional Complexity of Deterministic Restarting Automata.
In C. Mereghetti, B. Palano, G. Pighizzini, and D. Wotschke, editors,
Descriptional Complexity of Formal Systems, pages 158-169, Milano,
Italy, 2005. Universita degli Studi di Milano.
Abstract |
Technical Reports
| [1] |
M. Holzer and A. Maletti.
An n logn Algorithm for Hyper-Minimizing States in a
(Minimized) Deterministic Automaton.
IFIG Research Report 0902, Institut für Informatik,
Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen,
Germany, April 2009.
|
| [2] |
H. Gruber and M. Holzer.
Tight Bounds on the Descriptional Complexity of Regular
Expressions.
IFIG Research Report 0901, Institut für Informatik,
Justus-Liebig-Universität Gießen, Arndtstr. 2, D-35392 Gießen,
Germany, February 2009.
|
| [3] |
F. Brandt, F. Fischer, and M. Holzer.
On Iterated Dominance, Matrix Elimination, and Matched Paths.
Report TR08-077, Electronic Colloquium on Computational Complexity
(ECCC), August 2008.
PDF PS |
| [4] |
H. Gruber and M. Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
Technischer Bericht TUM-I0814, Institut für Informatik, Technische
Universität München, Boltzmannstraße 3, D-85748 Garching bei
München, Germany, May 2008.
PDF PS |
| [5] |
H. Gruber and M. Holzer.
Provably Shorter Regular Expressions from Deterministic Finite
Automata.
Technischer Bericht TUM-I0805, Institut für Informatik, Technische
Universität München, Boltzmannstraße 3, D-85748 Garching bei
München, Germany, February 2008.
PDF PS |
| [6] |
F. Brandt, F. Fischer, and M. Holzer.
Equilibria of Graphical Games with Symmetries.
Report TR07-136, Electronic Colloquium on Computational Complexity
(ECCC), December 2007.
PDF PS |
| [7] |
H. Gruber and M. Holzer.
Finite Automata, Digraph Connectivity, and Regular Expression
Size.
Technischer Bericht TUM-I0725, Institut für Informatik, Technische
Universität München, Boltzmannstraße 3, D-85748 Garching bei
München, Germany, December 2007.
PDF PS |
| [8] |
F. Brandt, F. Fischer, and M. Holzer.
Symmetries and the Complexity of Pure Nash Equilibrium.
Report TR06-091, Electronic Colloquium on Computational Complexity
(ECCC), August 2006.
PDF PS |
| [9] |
H. Gruber and M. Holzer.
Finding Lower Bounds for Nondeterministic State Complexity is
Hard.
Report TR06-027, Electronic Colloquium on Computational Complexity
(ECCC), March 2006.
PDF PS |
Parts of this pages were generated by bibtex2thml.