Markus Holzer

283 papers A* 1A 4B 12C 70Misc 9Journal 117Unranked 60
YearRankTypeTitle / Venue / Authors
2026 J jnl
On Jaffe's pumping lemma, revisited.
Inf. Comput.
Markus Holzer, Christian Rauch
2026 J jnl
The Pumping Lemma for Regular Languages is Hard.
Int. J. Found. Comput. Sci.
Hermann Gruber, Markus Holzer, Christian Rauch
2025 C conf
More on Language Families with a Decidable Pumping-Problem (Extended Abstract).
CIAA
Markus Holzer, Christian Rauch
2025 — conf
On Pumping Constants and Smallest Grammars for Context-Free Languages.
Languages of Cooperation and Communication
Hermann Gruber, Markus Holzer
2025 — conf
On Pumping Problems for Unary Regular Languages.
SOFSEM (2)
Hermann Gruber, Markus Holzer, Christian Rauch
2024 C conf
On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem (Extended Abstract).
CIAA
Hermann Gruber, Markus Holzer, Christian Rauch
2024 — conf
On Regular Expression Proof Complexity of Salomaa's Axiom System F
Taming the Infinities of Concurrency
Simon Beier, Markus Holzer
2024 C conf
On Switching Finite State Automata.
MCU
Joss Chapman, Markus Holzer, Petra Wolf
2024 J jnl
On the Complexity of Rolling Block, Colour, and Alice Mazes.
J. Autom. Lang. Comb.
Markus Holzer, Sebastian Jakobi
2024 C conf
The Pumping Lemma for Context-Free Languages is Undecidable.
DLT
Hermann Gruber, Markus Holzer, Christian Rauch
2023 C conf
Computational Complexity of Reversible Reaction Systems.
RC
Markus Holzer, Christian Rauch
2023 — conf
On Jaffe's Pumping Lemma, Revisited.
DCFS
Markus Holzer, Christian Rauch
2023 — conf
On Minimal Pumping Constants for Regular Languages.
AFL
Markus Holzer, Christian Rauch
2023 J jnl
On the accepting state complexity of operations on permutation automata.
RAIRO Theor. Informatics Appl.
Christian Rauch, Markus Holzer
2023 C conf
The Pumping Lemma for Regular Languages is Hard.
CIAA
Hermann Gruber, Markus Holzer, Christian Rauch
2023 J jnl
The Range of State Complexities of Languages Resulting from the Cascade Product - The Unary Case.
Int. J. Found. Comput. Sci.
Markus Holzer, Christian Rauch
2022 J jnl
Input-Driven Double-Head Pushdown Automata.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib, Andreas Malcher, Matthias Wendlandt
2022 J jnl
Nondeterministic right one-way jumping finite automata.
Inf. Comput.
Simon Beier, Markus Holzer
2022 C conf
On 25 Years of CIAA Through the Lens of Data Science.
CIAA
Hermann Gruber, Markus Holzer, Christian Rauch
2022 — conf
On the Accepting State Complexity of Operations on Permutation Automata.
NCMA
Christian Rauch, Markus Holzer
2022 — conf
On the Descriptional Complexity of the Direct Product of Finite Automata.
DCFS
Markus Holzer, Christian Rauch
2022 J jnl
Preface to Klaus-Jörn Lange Festschrift.
Acta Informatica
Henning Fernau, Markus Holzer, Petra Wolf
2021 — ch.
Descriptional complexity of regular languages.
Handbook of Automata Theory (I.)
Hermann Gruber, Markus Holzer, Martin Kutrib
2021 — conf
More on the Descriptional Complexity of Products of Finite Automata.
DCFS
Markus Holzer, Christian Rauch
2021 B conf
On Minimizing Regular Expressions Without Kleene Star.
FCT
Hermann Gruber, Markus Holzer, Simon Wolfsteiner
2021 — conf
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes.
FSTTCS
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, Petra Wolf
2021 J jnl
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes.
CoRR
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, Petra Wolf
2021 Misc conf
On the Computational Complexity of Reaction Systems, Revisited.
CSR
Markus Holzer, Christian Rauch
2021 J jnl
On the number of active states in finite automata.
Acta Informatica
Henning Bordihn, Markus Holzer
2021 B conf
Optimal Regular Expressions for Palindromes of Given Length.
MFCS
Hermann Gruber, Markus Holzer
2021 J jnl
Preface.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib
2021 J jnl
Preface: 11th Workshop on Non-classical Models of Automata and Applications (NCMA 2019).
RAIRO Theor. Informatics Appl.
Markus Holzer, José M. Sempere
2021 C conf
The Range of State Complexities of Languages Resulting from the Cascade Product - The General Case (Extended Abstract).
DLT
Markus Holzer, Christian Rauch
2021 C conf
The Range of State Complexities of Languages Resulting from the Cascade Product - The Unary Case (Extended Abstract).
CIAA
Markus Holzer, Christian Rauch
2021 J jnl
Two-Sided Strictly Locally Testable Languages.
Fundam. Informaticae
Markus Holzer, Martin Kutrib, Friedrich Otto
2020 J jnl
Automata That May Change Their Mind.
J. Autom. Lang. Comb.
Markus Holzer, Martin Kutrib
2020 J jnl
Decidability of Right One-Way Jumping Finite Automata.
Int. J. Found. Comput. Sci.
Simon Beier, Markus Holzer
2020 J jnl
On Minimizing Regular Expressions Without Kleene Star.
Electron. Colloquium Comput. Complex.
Hermann Gruber, Markus Holzer, Simon Wolfsteiner
2020 J jnl
The Ranges of Accepting State Complexities of Languages Resulting from Some Operations.
Int. J. Found. Comput. Sci.
Michal Hospodár, Markus Holzer
2019 — conf
A comment on strong language families and self-verifying complexity classes.
NCMA
Markus Holzer, Sebastian Jakobi
2019 J jnl
A mesh of automata.
Inf. Comput.
Sabine Broda, Markus Holzer, Eva Maia, Nelma Moreira, Rogério Reis
2019 B conf
Computational Complexity of Synchronization under Regular Constraints.
MFCS
Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, Petra Wolf
2019 — ed.
Eleventh Workshop on Non-Classical Models of Automata and Applications, NCMA 2019, Valencia, Spain, July 2-3, 2019.
NCMA
Rudolf Freund, Markus Holzer, José M. Sempere
2019 C conf
Non-Recursive Trade-Offs Are "Almost Everywhere".
CiE
Markus Holzer, Martin Kutrib
2019 — conf
Nondeterministic Right One-Way Jumping Finite Automata (Extended Abstract).
DCFS
Simon Beier, Markus Holzer
2019 J jnl
One-Time Nondeterministic Computations.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib
2019 J jnl
Operational State Complexity and Decidability of Jumping Finite Automata.
Int. J. Found. Comput. Sci.
Simon Beier, Markus Holzer, Martin Kutrib
2019 J jnl
Properties of right one-way jumping finite automata.
Theor. Comput. Sci.
Simon Beier, Markus Holzer
2019 C conf
Semi-linear Lattices and Right One-Way Jumping Finite Automata (Extended Abstract).
CIAA
Simon Beier, Markus Holzer
2019 C conf
The Range of State Complexities of Languages Resulting from the Cut Operation.
LATA
Markus Holzer, Michal Hospodár
2018 — conf
Automata that may change their mind.
NCMA
Markus Holzer, Martin Kutrib
2018 C conf
Computational Complexity of Decision Problems on Self-verifying Finite Automata.
DLT
Markus Holzer, Sebastian Jakobi, Jozef Jirásek Jr.
2018 C conf
Decidability of Right One-Way Jumping Finite Automata.
DLT
Simon Beier, Markus Holzer
2018 J jnl
Minimal Reversible Deterministic Finite Automata.
Int. J. Found. Comput. Sci.
Markus Holzer, Sebastian Jakobi, Martin Kutrib
2018 C conf
On Minimal Grammar Problems for Finite Languages.
DLT
Hermann Gruber, Markus Holzer, Simon Wolfsteiner
2018 J jnl
On bonded sequential and parallel insertion systems.
RAIRO Theor. Informatics Appl.
Markus Holzer, Bianca Truthe, Ahmad Firdaus Yosman
2018 — conf
On the Grammatical Complexity of Finite Languages.
DCFS
Markus Holzer, Simon Wolfsteiner
2018 J jnl
On the computational complexity of problems related to distinguishability sets.
Inf. Comput.
Markus Holzer, Sebastian Jakobi
2018 — conf
Properties of Right One-Way Jumping Finite Automata.
DCFS
Simon Beier, Markus Holzer
2018 Misc conf
Selection Via the Bogo-Method - More on the Analysis of Perversely Awful Randomized Algorithms.
FUN
Markus Holzer, Jan-Tobias Maurer
2018 C conf
The Ranges of Accepting State Complexities of Languages Resulting From Some Operations.
CIAA
Michal Hospodár, Markus Holzer
2017 — conf
Input-Driven Double-Head Pushdown Automata.
AFL
Markus Holzer, Martin Kutrib, Andreas Malcher, Matthias Wendlandt
2017 J jnl
More on Minimizing Finite Automata with Errors - Nondeterministic Machines.
Int. J. Found. Comput. Sci.
Markus Holzer, Sebastian Jakobi
2017 J jnl
More on deterministic and nondeterministic finite cover automata.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer, Sebastian Jakobi
2017 C conf
On Regular Expression Proof Complexity.
DLT
Simon Beier, Markus Holzer
2017 — conf
On the Descriptional Complexity of Operations on Semilinear Sets.
AFL
Simon Beier, Markus Holzer, Martin Kutrib
2017 C conf
On the Mother of All Automata: The Position Automaton.
DLT
Sabine Broda, Markus Holzer, Eva Maia, Nelma Moreira, Rogério Reis
2017 C conf
On the Number of Active States in Deterministic and Nondeterministic Finite Automata.
CIAA
Henning Bordihn, Markus Holzer
2017 — conf
One-Time Nondeterministic Computations.
DCFS
Markus Holzer, Martin Kutrib
2017 C conf
Operational State Complexity and Decidability of Jumping Finite Automata.
DLT
Simon Beier, Markus Holzer, Martin Kutrib
2017 C conf
Reversible Nondeterministic Finite Automata.
RC
Markus Holzer, Martin Kutrib
2017 — conf
Structure and Complexity of Some Subregular Language Families.
The Role of Theory in Computer Science
Markus Holzer, Martin Kutrib
2017 J jnl
The Degree of Irreversibility in Deterministic Finite Automata.
Int. J. Found. Comput. Sci.
Holger Bock Axelsen, Markus Holzer, Martin Kutrib
2017 J jnl
The chop of languages.
Theor. Comput. Sci.
Markus Holzer, Sebastian Jakobi, Martin Kutrib
2017 J jnl
Tight Bounds for Cut-Operations on Deterministic Finite Automata.
Fundam. Informaticae
Frank Drewes, Markus Holzer, Sebastian Jakobi, Brink van der Merwe
2017 — conf
Two-sided strictly locally testable languages.
NCMA
Markus Holzer, Martin Kutrib, Friedrich Otto
2016 J jnl
Boundary sets of regular and context-free languages.
Theor. Comput. Sci.
Markus Holzer, Sebastian Jakobi
2016 J jnl
Editorial.
J. Autom. Lang. Comb.
Markus Holzer, Martin Kutrib, Bianca Truthe
2016 J jnl
Minimal and Hyper-Minimal Biautomata.
Int. J. Found. Comput. Sci.
Markus Holzer, Sebastian Jakobi
2016 — conf
On bonded sequential and parallel insertion systems.
NCMA
Wan Heng Fong, Markus Holzer, Bianca Truthe, Sherzod Turaev, Ahmad Firdaus Yosman
2016 J jnl
On the Computational Complexity of Partial Word Automata Problems.
Fundam. Informaticae
Markus Holzer, Sebastian Jakobi, Matthias Wendlandt
2016 J jnl
Preface.
J. Autom. Lang. Comb.
Markus Holzer, Martin Kutrib, Bianca Truthe
2016 C conf
Reversible Shrinking Two-Pushdown Automata.
LATA
Holger Bock Axelsen, Markus Holzer, Martin Kutrib, Andreas Malcher
2016 C conf
The Degree of Irreversibility in Deterministic Finite Automata.
CIAA
Holger Bock Axelsen, Markus Holzer, Martin Kutrib
2015 J jnl
From Finite Automata to Regular Expressions and Back - A Summary on Descriptional Complexity.
Int. J. Found. Comput. Sci.
Hermann Gruber, Markus Holzer
2015 C conf
Minimal Reversible Deterministic Finite Automata.
DLT
Markus Holzer, Sebastian Jakobi, Martin Kutrib
2015 J jnl
Minimization and Characterizations for Biautomata.
Fundam. Informaticae
Markus Holzer, Sebastian Jakobi
2015 C conf
More on Deterministic and Nondeterministic Finite Cover Automata - Extended Abstract.
CIAA
Hermann Gruber, Markus Holzer, Sebastian Jakobi
2015 — conf
On relations between some subregular language families.
NCMA
Markus Holzer, Bianca Truthe
2015 — conf
On the Computational Complexity of Problems Related to Distinguishability Sets.
DCFS
Markus Holzer, Sebastian Jakobi
2015 J jnl
Preface.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib
2015 — ed.
Seventh Workshop on Non-Classical Models of Automata and Applications - NCMA 2015, Porto, Portugal, August 31 - September 1, 2015. Proceedings
NCMA
Rudolf Freund, Markus Holzer, Nelma Moreira, Rogério Reis
2015 J jnl
The Finite Index Restriction Meets Hybrid Modes in Cooperating Distributed Grammar Systems.
Int. J. Found. Comput. Sci.
Henning Fernau, Rudolf Freund, Markus Holzer
2015 C conf
Tight Bounds for Cut-Operations on Deterministic Finite Automata.
MCU
Frank Drewes, Markus Holzer, Sebastian Jakobi, Brink van der Merwe
2014 — conf
Boundary Sets of Regular and Context-Free Languages.
DCFS
Markus Holzer, Sebastian Jakobi
2014 — conf
Cooperating Distributed Grammar Systems of Finite Index Working in Hybrid Modes.
AFL
Henning Fernau, Rudolf Freund, Markus Holzer
2014 — conf
From Finite Automata to Regular Expressions and Back-A Summary on Descriptional Complexity.
AFL
Hermann Gruber, Markus Holzer
2014 C ed.
Implementation and Application of Automata - 19th International Conference, CIAA 2014, Giessen, Germany, July 30 - August 2, 2014. Proceedings
CIAA
Markus Holzer, Martin Kutrib
2014 C conf
Minimal and Hyper-Minimal Biautomata - (Extended Abstract).
Developments in Language Theory
Markus Holzer, Sebastian Jakobi
2014 — conf
More Structural Characterizations of Some Subregular Language Families by Biautomata.
AFL
Markus Holzer, Sebastian Jakobi
2014 J jnl
Nondeterministic Biautomata and their Descriptional Complexity.
Int. J. Found. Comput. Sci.
Markus Holzer, Sebastian Jakobi
2014 — conf
On the computational complexity of partial word automata problems.
NCMA
Markus Holzer, Sebastian Jakobi, Matthias Wendlandt
2014 J jnl
Preface.
RAIRO Theor. Informatics Appl.
Markus Holzer, Bianca Truthe
2014 J jnl
Self-Assembling Pushdown Automata.
J. Autom. Lang. Comb.
Markus Holzer, Martin Kutrib
2014 C conf
ω-rational Languages: High Complexity Classes vs. Borel Hierarchy.
LATA
Enrico Formenti, Markus Holzer, Martin Kutrib, Julien Provillard
2013 C conf
Brzozowski's Minimization Algorithm - More Robust than Expected - (Extended Abstract).
CIAA
Markus Holzer, Sebastian Jakobi
2013 J jnl
From Equivalence to Almost-Equivalence, and beyond: Minimizing Automata with Errors.
Int. J. Found. Comput. Sci.
Markus Holzer, Sebastian Jakobi
2013 — conf
Minimization and characterizations for biautomata.
NCMA
Markus Holzer, Sebastian Jakobi
2013 — conf
Nondeterministic Biautomata and Their Descriptional Complexity.
DCFS
Markus Holzer, Sebastian Jakobi
2013 J jnl
Provably Shorter Regular Expressions from Finite Automata.
Int. J. Found. Comput. Sci.
Hermann Gruber, Markus Holzer
2012 — conf
A Note on Combined Derivation Modes for Cooperating Distributed Grammar Systems.
Languages Alive
Markus Holzer
2012 J jnl
Descriptional Complexity of Chop Operations on Unary and Finite Languages.
J. Autom. Lang. Comb.
Markus Holzer, Sebastian Jakobi
2012 — ed.
Fourth Workshop on Non-Classical Models for Automata and Applications - NCMA 2012, Fribourg, Switzerland, August 23-24, 2012. Proceedings
NCMA
Rudolf Freund, Markus Holzer, Bianca Truthe, Ulrich Ultes-Nitsche
2012 C conf
From Equivalence to Almost-Equivalence, and Beyond - Minimizing Automata with Errors - (Extended Abstract).
Developments in Language Theory
Markus Holzer, Sebastian Jakobi
2012 C conf
Generalized Derivations with Synchronized Context-Free Grammars.
Developments in Language Theory
Markus Holzer, Sebastian Jakobi, Ian McQuillan
2012 Misc conf
Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes.
FUN
Markus Holzer, Sebastian Jakobi
2012 — conf
Input-Driven Stack Automata.
IFIP TCS
Suna Bensch, Markus Holzer, Martin Kutrib, Andreas Malcher
2012 J jnl
Nondeterministic state complexity of star-free languages.
Theor. Comput. Sci.
Markus Holzer, Martin Kutrib, Katja Meckel
2012 Misc conf
On Computer Integrated Rationalized Crossword Puzzle Manufacturing.
FUN
Jakob Engel, Markus Holzer, Oliver Ruepp, Frank Sehnke
2012 — conf
On Inverse Operations and Their Descriptional Complexity.
DCFS
Maria Paola Bianchi, Markus Holzer, Sebastian Jakobi, Giovanni Pighizzini
2012 J jnl
On Inverse Operations and Their Descriptional Complexity.
J. Autom. Lang. Comb.
Maria Paola Bianchi, Markus Holzer, Sebastian Jakobi, Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini
2012 Misc conf
On the Complexity of Rolling Block and Alice Mazes.
FUN
Markus Holzer, Sebastian Jakobi
2012 J jnl
Preface.
Theor. Comput. Sci.
Markus Holzer, Martin Kutrib, Giovanni Pighizzini
2012 J jnl
Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011).
RAIRO Theor. Informatics Appl.
Rudolf Freund, Markus Holzer, Carlo Mereghetti, Friedrich Otto, Beatrice Palano
2012 — conf
State Complexity of Chop Operations on Unary and Finite Languages.
DCFS
Markus Holzer, Sebastian Jakobi
2012 J jnl
The Magic Number Problem for Subregular Language Families.
Int. J. Found. Comput. Sci.
Markus Holzer, Sebastian Jakobi, Martin Kutrib
2011 C conf
Chop Operations and Expressions: Descriptional Complexity Considerations.
Developments in Language Theory
Markus Holzer, Sebastian Jakobi
2011 J jnl
Complexity of multi-head finite automata: Origins and directions.
Theor. Comput. Sci.
Markus Holzer, Martin Kutrib, Andreas Malcher
2011 J jnl
Computational Complexity of NURIKABE.
Fundam. Informaticae
Markus Holzer, Andreas Klein, Martin Kutrib, Oliver Ruepp
2011 — conf
Cooperating Distributed Grammar Systems: Components with Nonincreasing Competence.
Computation, Cooperation, and Life
Maurice H. ter Beek, Erzsébet Csuhaj-Varjú, Markus Holzer, György Vaszil
2011 J jnl
Decidability of operation problems for T0L languages and subclasses.
Inf. Comput.
Henning Bordihn, Markus Holzer, Martin Kutrib
2011 — ed.
Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings
DCFS
Markus Holzer, Martin Kutrib, Giovanni Pighizzini
2011 J jnl
Descriptional and computational complexity of finite automata - A survey.
Inf. Comput.
Markus Holzer, Martin Kutrib
2011 J jnl
Equilibria of graphical games with symmetries.
Theor. Comput. Sci.
Felix Brandt, Felix A. Fischer, Markus Holzer
2011 C conf
Gaining Power by Input Operations: Finite Automata and Beyond.
CIAA
Markus Holzer, Martin Kutrib
2011 J jnl
Hairpin Finite Automata.
J. Autom. Lang. Comb.
Henning Bordihn, Markus Holzer, Martin Kutrib
2011 C conf
Nodes Connected by Path Languages.
Developments in Language Theory
Markus Holzer, Martin Kutrib, Ursula Leiter
2011 C conf
Nondeterministic State Complexity of Star-Free Languages.
CIAA
Markus Holzer, Martin Kutrib, Katja Meckel
2011 J jnl
On the size of inverse semigroups given by generators.
Theor. Comput. Sci.
Martin Beaudry, Markus Holzer
2011 J jnl
Preface.
Fundam. Informaticae
Henning Bordihn, Rudolf Freund, Mika Hirvensalo, Markus Holzer, Martin Kutrib, Friedrich Otto
2011 — conf
The Chop of Languages.
AFL
Markus Holzer, Sebastian Jakobi, Martin Kutrib
2011 J jnl
The Complexity of Regular(-like) Expressions.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib
2011 — ed.
Third Workshop on Non-Classical Models for Automata and Applications - NCMA 2011, Milan, Italy, July 18 - July 19, 2011. Proceedings
NCMA
Rudolf Freund, Markus Holzer, Carlo Mereghetti, Friedrich Otto, Beatrice Palano
2010 J jnl
An nlogn algorithm for hyper-minimizing a (minimized) deterministic automaton.
Theor. Comput. Sci.
Markus Holzer, Andreas Maletti
2010 — conf
Cellular Automata and the Quest for Nontrivial Artificial Self-Reproduction.
Int. Conf. on Membrane Computing
Markus Holzer, Martin Kutrib
2010 — ch.
Descriptional Complexity - An Introductory Survey.
Scientific Applications of Language Methods
Markus Holzer, Martin Kutrib
2010 — conf
Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata.
RP
Markus Holzer, Martin Kutrib
2010 J jnl
Extending regular expressions with homomorphic replacement.
RAIRO Theor. Informatics Appl.
Henning Bordihn, Jürgen Dassow, Markus Holzer
2010 J jnl
On Iterated Dominance, Matrix Elimination, and Matched Paths
CoRR
Felix Brandt, Felix A. Fischer, Markus Holzer
2010 A conf
On Iterated Dominance, Matrix Elimination, and Matched Paths.
STACS
Felix Brandt, Felix A. Fischer, Markus Holzer
2010 J jnl
On Measuring Non-recursive Trade-Offs.
J. Autom. Lang. Comb.
Hermann Gruber, Markus Holzer, Martin Kutrib
2010 — ed.
Second Workshop on Non-Classical Models for Automata and Applications - NCMA 2010, Jena, Germany, August 23 - August 24, 2010. Proceedings
NCMA
Henning Bordihn, Rudolf Freund, Markus Holzer, Thomas Hinze, Martin Kutrib, Friedrich Otto
2010 C conf
The Complexity of Regular(-Like) Expressions.
Developments in Language Theory
Markus Holzer, Martin Kutrib
2010 Misc conf
The Computational Complexity of RaceTrack.
FUN
Markus Holzer, Pierre McKenzie
2010 Misc conf
The Computational Complexity of the Kakuro Puzzle, Revisited.
FUN
Oliver Ruepp, Markus Holzer
2010 — conf
The Magic Number Problem for Subregular Language Families
DCFS
Markus Holzer, Sebastian Jakobi, Martin Kutrib
2009 C conf
An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton.
CIAA
Markus Holzer, Andreas Maletti
2009 C conf
Descriptional and Computational Complexity of Finite Automata.
LATA
Markus Holzer, Martin Kutrib
2009 J jnl
Determination of finite automata accepting subregular languages.
Theor. Comput. Sci.
Henning Bordihn, Markus Holzer, Martin Kutrib
2009 J jnl
Language operations with regular expressions of polynomial size.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer
2009 J jnl
More on the Size of Higman-Haines Sets: Effective Constructions.
Fundam. Informaticae
Hermann Gruber, Markus Holzer, Martin Kutrib
2009 J jnl
Nondeterministic Finite Automata - Recent Results on the Descriptional and Computational Complexity.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib
2009 — conf
On Measuring Non-Recursive Trade-Offs
DCFS
Hermann Gruber, Markus Holzer, Martin Kutrib
2009 J jnl
On input-revolving deterministic and nondeterministic finite automata.
Inf. Comput.
Suna Bensch, Henning Bordihn, Markus Holzer, Martin Kutrib
2009 J jnl
On the uniqueness of shuffle on words and finite languages.
Theor. Comput. Sci.
Franziska Biegler, Mark Daley, Markus Holzer, Ian McQuillan
2009 C conf
Short Regular Expressions from Finite Automata: Empirical Results.
CIAA
Hermann Gruber, Markus Holzer, Michael Tautschnig
2009 J jnl
Symmetries and the complexity of pure Nash equilibrium.
J. Comput. Syst. Sci.
Felix Brandt, Felix A. Fischer, Markus Holzer
2009 C conf
Tight Bounds on the Descriptional Complexity of Regular Expressions.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2009 C conf
Undecidability of Operation Problems for T0L Languages and Subclasses.
LATA
Henning Bordihn, Markus Holzer, Martin Kutrib
2009 — ed.
Workshop on Non-Classical Models for Automata and Applications - NCMA 2009, Wroclaw, Poland, August 31 - September 1, 2009. Proceedings
NCMA
Henning Bordihn, Rudolf Freund, Markus Holzer, Martin Kutrib, Friedrich Otto
2008 J jnl
A note on cooperating distributed grammar systems working in combined modes.
Inf. Process. Lett.
Henning Bordihn, Markus Holzer
2008 C conf
Deterministic Input-Reversal and Input-Revolving Finite Automata.
LATA
Suna Bensch, Henning Bordihn, Markus Holzer, Martin Kutrib
2008 — conf
Equilibria of Graphical Games with Symmetries.
WINE
Felix Brandt, Felix A. Fischer, Markus Holzer
2008 — conf
Finite Automata, Digraph Connectivity, and Regular Expression Size.
ICALP (2)
Hermann Gruber, Markus Holzer
2008 — conf
Language Operations with Regular Expressions of Polynomial Size.
DCFS
Hermann Gruber, Markus Holzer
2008 — conf
Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
CSP
Markus Holzer, Martin Kutrib, Andreas Malcher
2008 C conf
Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity.
CIAA
Markus Holzer, Martin Kutrib
2008 J jnl
On Iterated Dominance, Matrix Elimination, and Matched Paths.
Electron. Colloquium Comput. Complex.
Felix Brandt, Felix A. Fischer, Markus Holzer
2008 C conf
Provably Shorter Regular Expressions from Deterministic Finite Automata.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2008 C conf
Random Context in Regulated Rewriting VersusCooperating Distributed Grammar Systems.
LATA
Henning Bordihn, Markus Holzer
2008 — conf
State Complexity of NFA to DFA Conversion of Subregular Language Families.
DCFS
Henning Bordihn, Markus Holzer, Martin Kutrib
2007 C conf
Computational Complexity of NFA Minimization for Finite and Unary Languages.
LATA
Hermann Gruber, Markus Holzer
2007 J jnl
Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited.
Fundam. Informaticae
Henning Bordihn, Markus Holzer
2007 J jnl
Equilibria of Graphical Games with Symmetries.
Electron. Colloquium Comput. Complex.
Felix Brandt, Felix A. Fischer, Markus Holzer
2007 C conf
Hairpin Finite Automata.
Developments in Language Theory
Henning Bordihn, Markus Holzer, Martin Kutrib
2007 J jnl
Hybrid Extended Finite Automata.
Int. J. Found. Comput. Sci.
Henning Bordihn, Markus Holzer, Martin Kutrib
2007 C conf
Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2007 C conf
More on the Size of Higman-Haines Sets: Effective Constructions.
MCU
Hermann Gruber, Markus Holzer, Martin Kutrib
2007 J jnl
Non-Recursive Trade-Offs for Deterministic Restarting Automata.
J. Autom. Lang. Comb.
Markus Holzer, Martin Kutrib, Jens Reimann
2007 J jnl
On Competence in CD Grammar Systems with Parallel Rewriting.
Int. J. Found. Comput. Sci.
Maurice H. ter Beek, Erzsébet Csuhaj-Varjú, György Vaszil, Markus Holzer
2007 J jnl
On the average state and transition complexity of finite languages.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer
2007 Misc conf
Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms.
FUN
Hermann Gruber, Markus Holzer, Oliver Ruepp
2007 A conf
Symmetries and the Complexity of Pure Nash Equilibrium.
STACS
Felix Brandt, Felix A. Fischer, Markus Holzer
2007 J jnl
The Complexity of Tensor Circuit Evaluation.
Comput. Complex.
Martin Beaudry, Markus Holzer
2007 Misc conf
The Troubles of Interior Design-A Complexity Analysis of the Game Heyawake.
FUN
Markus Holzer, Oliver Ruepp
2007 J jnl
The size of Higman-Haines sets.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer, Martin Kutrib
2006 J jnl
CD grammar systems with competence based entry conditions in their cooperation protocols.
Int. J. Comput. Math.
Erzsébet Csuhaj-Varjú, Jürgen Dassow, Markus Holzer
2006 C conf
Finding Lower Bounds for Nondeterministic State Complexity Is Hard.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2006 J jnl
Finding Lower Bounds for Nondeterministic State Complexity is Hard.
Electron. Colloquium Comput. Complex.
Hermann Gruber, Markus Holzer
2006 C conf
Hybrid Extended Finite Automata.
CIAA
Henning Bordihn, Markus Holzer, Martin Kutrib
2006 J jnl
Iterated sequential transducers as language generating devices.
Theor. Comput. Sci.
Henning Bordihn, Henning Fernau, Markus Holzer, Vincenzo Manca, Carlos Martín-Vide
2006 J jnl
Programmed grammars and their relation to the LBA problem.
Acta Informatica
Henning Bordihn, Markus Holzer
2006 — conf
Results on the Average State and Transition Complexity of Finite Automata Accepting Finite Languages (Extended Abstract).
DCFS
Hermann Gruber, Markus Holzer
2006 J jnl
Symmetries and the Complexity of Pure Nash Equilibrium.
Electron. Colloquium Comput. Complex.
Felix Brandt, Felix A. Fischer, Markus Holzer
2006 — conf
The Size of Higman-Haines Sets.
DCFS
Markus Holzer, Martin Kutrib
2006 J jnl
The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria.
Inf. Process. Lett.
Felix A. Fischer, Markus Holzer, Stefan Katzenbeisser
2006 J jnl
Variable Complexity of Simple Programs.
Fundam. Informaticae
Markus Holzer, Martin Kutrib
2005 J jnl
A common algebraic description for probabilistic and quantum computations
Theor. Comput. Sci.
Martin Beaudry, José M. Fernandez, Markus Holzer
2005 — conf
Descriptional Complexity of Deterministic Restarting Automata.
DCFS
Markus Holzer, Martin Kutrib, Jens Reimann
2005 J jnl
Language families defined by a ciliate bio-operation: hierarchies and decision problems.
Int. J. Found. Comput. Sci.
Jürgen Dassow, Markus Holzer
2005 C conf
On Timed Automata with Discrete Time - Structural and Language Theoretical Characterization.
Developments in Language Theory
Hermann Gruber, Markus Holzer, Astrid Kiehn, Barbara König
2005 J jnl
On the descriptional complexity of finite automata with modified acceptance conditions.
Theor. Comput. Sci.
Markus Holzer, Martin Kutrib
2005 J jnl
Representations of Recursively Enumerable Array Languages by Contextual Array Grammars.
Fundam. Informaticae
Henning Fernau, Rudolf Freund, Markus Holzer
2005 C conf
Revolving-Input Finite Automata.
Developments in Language Theory
Henning Bordihn, Markus Holzer, Martin Kutrib
2005 B conf
Shrinking Multi-pushdown Automata.
FCT
Markus Holzer, Friedrich Otto
2005 J jnl
Unsolvability levels of operation problems for subclasses of context-free languages.
Int. J. Found. Comput. Sci.
Henning Bordihn, Markus Holzer, Martin Kutrib
2004 B conf
A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract).
MFCS
Martin Beaudry, José M. Fernandez, Markus Holzer
2004 J jnl
Assembling molecules in ATOMIX is hard.
Theor. Comput. Sci.
Markus Holzer, Stefan Schwoon
2004 J jnl
Economy of Description for Basic Constructions on Rational Transductions.
J. Autom. Lang. Comb.
Henning Bordihn, Markus Holzer, Martin Kutrib
2004 C conf
Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages.
Developments in Language Theory
Henning Bordihn, Markus Holzer, Martin Kutrib
2004 C conf
On Competence in CD Grammar Systems.
Developments in Language Theory
Maurice H. ter Beek, Erzsébet Csuhaj-Varjú, Markus Holzer, György Vaszil
2004 J jnl
On deterministic finite automata and syntactic monoid size.
Theor. Comput. Sci.
Markus Holzer, Barbara König
2004 C conf
Register Complexity of LOOP-, WHILE-, and GOTO-Programs.
MCU
Markus Holzer, Martin Kutrib
2004 J jnl
Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other (Column: Formal Language Theory).
Bull. EATCS
Markus Holzer, Barbara König
2004 C conf
Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages.
CIAA
Henning Bordihn, Markus Holzer, Martin Kutrib
2004 J jnl
Tantrix
Discret. Appl. Math.
Markus Holzer, Waltraud Holzer
2004 — conf
Towards Formal Semantics for ODRL.
ODRL Workshop
Markus Holzer, Stefan Katzenbeisser, Christian Schallhart
2003 J jnl
Alternating and empty alternating auxiliary stack automata.
Theor. Comput. Sci.
Markus Holzer, Pierre McKenzie
2003 C conf
Flip-Pushdown Automata: Nondeterminism Is Better than Determinism.
Developments in Language Theory
Markus Holzer, Martin Kutrib
2003 A* conf
Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k.
ICALP
Markus Holzer, Martin Kutrib
2003 J jnl
Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes le k and =k.
Theor. Comput. Sci.
Henning Fernau, Markus Holzer, Rudolf Freund
2003 J jnl
McNaughton families of languages.
Theor. Comput. Sci.
Martin Beaudry, Markus Holzer, Gundula Niemann, Friedrich Otto
2003 J jnl
Nondeterministic Descriptional Complexity Of Regular Languages.
Int. J. Found. Comput. Sci.
Markus Holzer, Martin Kutrib
2003 C conf
On Deterministic Finite Automata and Syntactic Monoid Size, Continued.
Developments in Language Theory
Markus Holzer, Barbara König
2003 — conf
On Iterated Sequential Transducers.
Grammars and Automata for String Processing
Henning Bordihn, Henning Fernau, Markus Holzer
2003 — conf
On the Descriptional Complexity of Finite Automata With Modified Acceptance Conditions.
DCFS
Markus Holzer
2002 — conf
Economy of Descriptions for Basic Constructions on Rational Transductions.
DCFS
Henning Bordihn, Markus Holzer, Martin Kutrib
2002 J jnl
Graph-Controlled Cooperating Distributed Grammar Systems with Singleton Components.
J. Autom. Lang. Comb.
Henning Fernau, Markus Holzer
2002 J jnl
Multi-head finite automata: data-independent versus data-dependent computations.
Theor. Comput. Sci.
Markus Holzer
2002 C conf
On Deterministic Finite Automata and Syntactic Monoid Size.
Developments in Language Theory
Markus Holzer, Barbara König
2002 J jnl
On the Computational Complexity of Synchronized Context-Free Languages.
J. Univers. Comput. Sci.
Henning Bordihn, Markus Holzer
2002 C conf
State Complexity of Basic Operations on Nondeterministic Finite Automata.
CIAA
Markus Holzer, Martin Kutrib
2002 J jnl
The complexity of tensor calculus.
Comput. Complex.
Carsten Damm, Markus Holzer, Pierre McKenzie
2002 C conf
Unary Language Operations and Their Nondeterministic State Complexity.
Developments in Language Theory
Markus Holzer, Martin Kutrib
2001 — conf
Graph-Controlled Cooperating Distributed Grammar Systems with Singleton Components.
DCFS
Henning Fernau, Markus Holzer
2001 J jnl
Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization.
Theor. Comput. Sci.
Henning Fernau, Markus Holzer, Rudolf Freund
2001 C conf
Improving Raster Image Run-Length Encoding Using Data Order.
CIAA
Markus Holzer, Martin Kutrib
2001 J jnl
On the Number of Active Symbols in L and CD Grammar Systems.
J. Autom. Lang. Comb.
Henning Bordihn, Markus Holzer
2001 C conf
On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy.
Developments in Language Theory
Martin Beaudry, Markus Holzer, Gundula Niemann, Friedrich Otto
2001 J jnl
On the State Complexity of k-Entry Deterministic Finite Automata.
J. Autom. Lang. Comb.
Markus Holzer, Kai Salomaa, Sheng Yu
2001 B conf
The Complexity of Tensor Circuit Evaluation.
MFCS
Martin Beaudry, Markus Holzer
2000 B conf
Alternating and Empty Alternating Auxiliary Stack Automata.
MFCS
Markus Holzer, Pierre McKenzie
2000 — conf
External Contextual and Conditional Languages.
Recent Topics in Mathematical and Computational Linguistics
Henning Fernau, Markus Holzer
2000 J jnl
Grammar Systems with Negated Conditions in their Cooperation Protocols
J. Univers. Comput. Sci.
Henning Bordihn, Markus Holzer
2000 J jnl
The Complexity of Tensor Calculus
Electron. Colloquium Comput. Complex.
Carsten Damm, Markus Holzer, Pierre McKenzie
2000 A conf
The Complexity of Tensor Calculus.
CCC
Carsten Damm, Markus Holzer, Pierre McKenzie
1999 C conf
Cooperating distributed grammar systems with non-terminating components.
Developments in Language Theory
Henning Bordihn, Markus Holzer
1999 J jnl
On Accepting Pure Lindenmayer Systems.
Fundam. Informaticae
Henning Bordihn, Henning Fernau, Markus Holzer
1999 J jnl
On a Hierarchy of Languages Generated by Cooperating Distributed Grammar Systems.
Inf. Process. Lett.
Henning Bordihn, Markus Holzer
1999 C conf
On fixed and general membership for external and internal contextual languages.
Developments in Language Theory
Markus Holzer
1999 — conf
Regulated Array Grammars of Finite Index. Part I: Theoretical Investigations.
Grammatical Models of Multi-Agent Systems
Henning Fernau, Rudolf Freund, Markus Holzer
1999 — conf
Regulated Array Grammars of Finite Index. Part II: Syntactic Pattern Recognition.
Grammatical Models of Multi-Agent Systems
Henning Fernau, Rudolf Freund, Markus Holzer
1998 — conf
Character Recognition with
SSPR/SPR
Henning Fernau, Rudolf Freund, Markus Holzer
1998 — —
Data-independent versus data-dependent computations on multi-head automata.
Markus Holzer
1998 — conf
The Generative Power of
MCU (2)
Henning Fernau, Rudolf Freund, Markus Holzer
1998 A conf
VisA: A Tool for Visualizing and Animating Automata and Formal Languages.
GD
Markus Holzer, Muriel Quenzer
1998 — conf
VisA: towards a students' green card to automata theory and formal languages.
ACSE
Markus Holzer, Muriel Quenzer
1997 C conf
Bounding resources in Cooperating Distributed Grammar Systems.
Developments in Language Theory
Henning Fernau, Markus Holzer, Rudolf Freund
1997 — conf
Conditional Context-Free Languages of Finite Index.
New Trends in Formal Languages
Henning Fernau, Markus Holzer
1997 J jnl
Expressing Uniformity via Oracles.
Theory Comput. Syst.
Carsten Damm, Markus Holzer, Peter Rossmanith
1997 B conf
Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations.
MFCS
Markus Holzer
1997 — conf
On the Complexity of Iterated Insertions.
New Trends in Formal Languages
Markus Holzer, Klaus-Jörn Lange
1996 J jnl
Accepting Multi-Agent Systems II.
Acta Cybern.
Henning Fernau, Markus Holzer
1996 J jnl
Accepting Multi-Agent Systems.
Comput. Artif. Intell.
Henning Fernau, Markus Holzer, Henning Bordihn
1996 J jnl
Inductive Counting for Width-Restricted Branching Programs.
Inf. Comput.
Carsten Damm, Markus Holzer
1995 B conf
Automata That Take Advice.
MFCS
Carsten Damm, Markus Holzer
1995 J jnl
Expressing Uniformity via Oracles
Universität Trier, Mathematik/Informatik, Forschungsbericht
Carsten Damm, Markus Holzer, Peter Rossmanith
1995 C conf
On Emptiness and Counting for Alternating Finite Automata.
Developments in Language Theory
Markus Holzer
1994 B conf
Inductive Counting Below LOGSPACE.
MFCS
Carsten Damm, Markus Holzer
1994 J jnl
Inductive Counting below LOGSPACE
Universität Trier, Mathematik/Informatik, Forschungsbericht
Carsten Damm, Markus Holzer
1993 C conf
Deterministic OL Languages are of Very Low Complexity: DOL is in AC
Developments in Language Theory
Carsten Damm, Markus Holzer, Klaus-Jörn Lange, Peter Rossmanith
1993 B conf
On the Complexities of Linear LL(1) and LR(1) Grammars.
FCT
Markus Holzer, Klaus-Jörn Lange
1992 B conf
Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers.
MFCS
Carsten Damm, Markus Holzer, Klaus-Jörn Lange