Publications


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

Journal Articles

[1] M. Holzer and S. Jakobi. Minimal and Hyper-Minimal Biautomata. International Journal of Foundations of Computer Science, 27(2):161-185, February 2016.
DOI  Abstract
[2] M. Holzer and S. Jakobi. Boundary Sets of Regular and Context-Free Languages. Theoretical Computer Science, 610, Part A:59-77, January 2016.
DOI  Abstract
[3] H. Gruber and M. Holzer. From Finite Automata to Regular Expressions and Back-A Summary on Descriptional Complexity. International Journal of Foundations of Computer Science, 26(8):1009-1040, December 2015.
DOI  Abstract
[4] H. Fernau, R. Freund, and M. Holzer. The Finite Index Restriction Meets Hybrid Modes in Cooperating Distributed Grammar Systems. International Journal of Foundations of Computer Science, 26(8):1167-1188, December 2015.
DOI  Abstract
[5] M. Holzer and S. Jakobi. Minimization and Characterizations for Biautomata. Fundamenta Informaticae, 136(1-2):1-25, 2015.
DOI
[6] M. Holzer and S. Jakobi. Nondeterministic Biautomata and Their Descriptional Complexity. International Journal of Foundations of Computer Science, 25(7):837-855, November 2014.
DOI  Abstract
[7] M. Holzer and S. Jakobi. From Equivalence to Almost-Equivalence, and Beyond: Minimizing Automata With Errors. International Journal of Foundations of Computer Science, 24(7):1083-1134, November 2013.
DOI  Abstract
[8] H. Gruber and M. Holzer. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science, 24(8):1255-1279, November 2013.
DOI  Abstract
[9] M. Holzer, M. Kutrib, and K. Meckel. Nondeterministic State Complexity of Star-Free Languages. Theoretical Computer Science, 450:68-80, September 2012.
DOI  Abstract
[10] M. Holzer, S. Jakobi, and M. Kutrib. The Magic Number Problem for Subregular Language Families. International Journal of Foundations of Computer Science, 23(1):115-131, January 2012.
DOI  Abstract
[11] M. P. Bianchi, M. Holzer, S. Jakobi, C. Mereghetti, B. Palano, and G. Pighizzini. On Inverse Operations and Their Descriptional Complexity. Journal of Automata, Languages and Combinatorics, 17(2-4):61-81, 2012.
Abstract
[12] M. Holzer and S. Jakobi. Descriptional Complexity of Chop Operations on Unary and Finite Languages. Journal of Automata, Languages and Combinatorics, 17(2-4):165-183, 2012.
Abstract

Books and Invited Papers

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

Conferences

[1] F. W. Heng, M. Holzer, B. Truthe, S. Turaev, and A. F. Yosman. On Bounded Sequential and Parallel Insertion Systems. In H. Bordihn, R. Freund, B. Nagy, and G. Vaszil, editors, Proceedings of the 8th International Workshop on Non-Classical Models of Automata and Applications, number 321 in books@ocg.at, pages 163-178, Debrecen, Hungary, August 2016. Österreichische Computer Gesellschaft.
[2] H. B. Axelsen, M. Holzer, and M. Kutrib. The Degree of Irreversibility in Deterministic Finite Automata. In Y.-S. Han and K. Salomaa, editors, Proceedings of the 21st Conference on Implementation and Application of Automata, number 9705 in LNCS, pages 15-26, Seoul, South Korea, July 2016. Springer.
DOI  Abstract
[3] H. B. Axelsen, M. Holzer, M. Kutrib, and A. Malcher. Reversible Shrinking Two-Pushdown Automata. In A. H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, editors, Proceedings of the 10th International Conference Language and Automata Theory and Applications, number 9618 in LNCS, pages 579-591, Prague, Czech Republic, March 2016. Springer.
DOI  Abstract
[4] F. Drewes, M. Holzer, S. Jakobi, and B. van der Merwe. Tight Bounds for Cut-Operations on Deterministic Finite Automata. In J. Durand-Lose and B. Nagy, editors, Proceedings of the 7th International Conference Machines, Computations, and Universality, number 9288 in LNCS, pages 45-60, Famagusta, North Cyprus, September 2015. Springer.
DOI  Abstract
[5] H. Gruber, M. Holzer, and S. Jakobi. More on Deterministic and Nondeterministic Finite Cover Automata. In F. Drewes, editor, Proceedings of the 20th Conference on Implementation and Application of Automata, number 9223 in LNCS, pages 114-126, Umea, Sweden, August 2015. Springer.
DOI  Abstract
[6] M. Holzer and S. Jakobi. On the Computational Complexity of Problems Related to Distinguishability Sets. In J. Shallit and A. Okhotin, editors, Proceedings of the 17th Workshop on Deescriptional Complexity of Formal Systems, number 9118 in LNCS, pages 117-128, Waterloo, Ontario, Canada, July 2015. Springer.
DOI  Abstract
[7] M. Holzer, S. Jakobi, and M. Kutrib. Minimal Reversible Deterministic Finite Automata. In I. Potapov, editor, Proceedings of the 19th International Conference Developments in Language Theory, number 9168 in LNCS, pages 276-287, Liverpool, UK, July 2015. Springer.
DOI  Abstract
[8] M. Holzer and S. Jakobi. Boundary Sets of Regular and Context-Free Languages. In H. Jürgensen, j. Karhumäki, and A. Okhotin, editors, Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems, number 8614 in LNCS, pages 162-173, Turku, Finland, August 2014. Springer.
DOI  Abstract
[9] M. Holzer and S. Jakobi. Minimal and Hyper-Minimal Biautomata. In A. M. Shur and M. V. Volkov, editors, Proceedings of the 18th International Conference Developments in Language Theory, number 8633 in LNCS, pages 291-302, Ekaterinburg, Russia, August 2014. Springer.
DOI  Abstract
[10] M. Holzer, S. Jakobi, and Matthias Wendlandt. On the Computational Complexity of Partial Word Automata Problems. In S. Bensch, R. Freund, and F. Otto, editors, Proceedings of the 6th International Workshop on Non-Classical Models of Automata and Applications, number 304 in books@ocg.at, pages 131-146, Kassel, Germany, July 2014. Österreichische Computer Gesellschaft.
[11] H. Fernau, R. Freund, and M. Holzer. Cooperating Distributed Grammar Systems of Finite Index Working in Hybrid Modes. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 14th International Conference on Automata and Formal Languages, number 151 in EPTCS, pages 246-260, Szeged, Hungary, May 2014.
DOI  Abstract
[12] M. Holzer and S. Jakobi. More Structural Characterizations of Some Subregular Language Families by Biautomata. In Z. Ésik and Z. Fülöp, editors, Proceedings of the 14th International Conference on Automata and Formal Languages, number 151 in EPTCS, pages 271-285, Szeged, Hungary, May 2014.
DOI  Abstract
[13] E. Formenti, M. Holzer, M. Kutrib, and J. Provillard. ω-Rational Languages: High Complexity Classes vs. Borel Hierarchy. In A. H. Dediu, C. Martín-Vide, J. L. Sierra-Rodríguez, and B. Truthe, editors, Proceedings of the 8th International Conference on Language and Automata Theory and Applications, number 8270 in LNCS, pages 372-282, Madrid, Spain, March 2014. Springer.
DOI  Abstract
[14] M. Holzer and S. Jakobi. Minimization and Characterizations for Biautomata. In S. Bensch, F. Drewes, R. Freund, and F. Otto, editors, Proceedings of the 5th International Workshop on Non-Classical Models of Automata and Applications, number 294 in books@ocg.at, pages 179-193, Umeå, Sweden, August 2013. Österreichische Computer Gesellschaft.
Abstract
[15] M. Holzer and S. Jakobi. Brzozowski's Minimization Algorithm-More Robust than Expected (Extended Abstract). In S. Konstantinidis, editor, Proceedings of the 18th International Conference on Implementation and Application of Automata, number 7982 in LNCS, pages 181-192, Halifax, Nova Scotia, Canada, July 2013. Springer.
DOI  Abstract
[16] M. Holzer and S. Jakobi. Nondeterministic Biautomata and Their Descriptional Complexity. In H. Jürgensen and R. Reis, editors, Proceedings of the 15th International Workshop on Descriptional Complexity of Formal Systems, number 8031 in LNCS, pages 112-123, London, Ontario, Canada, July 2013. Springer.
DOI  Abstract
[17] M. Holzer and S. Jakobi. From Equivalence to Almost-Equivalence, and Beyond-Minimizing Automata with Errors (Extended Abstract). In H.-C. Yen and O. H. Ibarra, editors, Proceedings of the 16th International Conference Developments in Language Theory, number 7410 in LNCS, pages 190-201, Taipei, Taiwan, August 2012. Springer.
DOI  Abstract
[18] M. Holzer, S. Jakobi, and I. McQuillan. General Derivations with Synchronzied Context-Free Grammars. In H.-C. Yen and O. H. Ibarra, editors, Proceedings of the 16th International Conference Developments in Language Theory, number 7410 in LNCS, pages 109-120, Taipei, Taiwan, August 2012. Springer.
DOI  Abstract
[19] M. Holzer and S. Jakobi. State Complexity of Chop Operations on Unary and Finite Languages. In M. Kutrib, N. Moreira, and R. Reis, editors, Proceedings of the 14th Workshop on Descriptional Complexity of Formal Systems, number 7386 in LNCS, pages 169-182, Braga, Portugal, July 2012. Springer.
DOI  Abstract
[20] M. P. Bianchi, M. Holzer, S. Jakobi, and G. Pighizzini. On Inverse Operations and Their Descriptional Complexity. In M. Kutrib, N. Moreira, and R. Reis, editors, Proceedings of the 14th Workshop on Descriptional Complexity of Formal Systems, number 7386 in LNCS, pages 89-102, Braga, Portugal, July 2012. Springer.
DOI  Abstract
[21] M. Holzer and S. Jakobi. Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International Conference on FUN with Algorithms, number 7288 in LNCS, pages 223-234, Venice, Italy, June 2012. Springer.
DOI  Abstract
[22] M. Holzer and S. Jakobi. On the Complexity of Rolling Block and Alice Mazes. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International Conference on FUN with Algorithms, number 7288 in LNCS, pages 210-222, Venice, Italy, June 2012. Springer.
DOI  Abstract
[23] J. Engel, M. Holzer, O. Ruepp, and F. Sehnke. On Computer Integrated Rationalized Crossword Puzzle Manufactering. In E. Kranakis, D. Krizanc, and F. Luccio, editors, Proceedings of the 6th International Conference on FUN with Algorithms, number 7288 in LNCS, pages 131-141, Venice, Italy, June 2012. Springer.
DOI  Abstract

Technical Reports

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

Parts of this pages were generated by bibtex2thml.