 | 2010 |
|---|
| 117 |       | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
On Iterated Dominance, Matrix Elimination, and Matched Paths
CoRR abs/1001.0529: (2010) |
| 2009 |
|---|
| 116 | | Hermann Gruber,
Markus Holzer,
Michael Tautschnig:
Short Regular Expressions from Finite Automata: Empirical Results.
CIAA 2009: 188-197 |
| 115 | | Markus Holzer,
Andreas Maletti:
An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton.
CIAA 2009: 4-13 |
| 114 | | Hermann Gruber,
Markus Holzer:
Tight Bounds on the Descriptional Complexity of Regular Expressions.
Developments in Language Theory 2009: 276-287 |
| 113 | | Markus Holzer,
Martin Kutrib:
Descriptional and Computational Complexity of Finite Automata.
LATA 2009: 23-42 |
| 112 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Undecidability of Operation Problems for T0L Languages and Subclasses.
LATA 2009: 236-246 |
| 111 | | Hermann Gruber,
Markus Holzer,
Martin Kutrib:
On Measuring Non-Recursive Trade-Offs
CoRR abs/0907.5063: (2009) |
| 110 | | Hermann Gruber,
Markus Holzer,
Martin Kutrib:
More on the Size of Higman-Haines Sets: Effective Constructions.
Fundam. Inform. 91(1): 105-121 (2009) |
| 109 | | Suna Bensch,
Henning Bordihn,
Markus Holzer,
Martin Kutrib:
On input-revolving deterministic and nondeterministic finite automata.
Inf. Comput. 207(11): 1140-1155 (2009) |
| 108 | | Markus Holzer,
Martin Kutrib:
Nondeterministic Finite Automata - Recent Results on the Descriptional and Computational Complexity.
Int. J. Found. Comput. Sci. 20(4): 563-580 (2009) |
| 107 | | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
Symmetries and the complexity of pure Nash equilibrium.
J. Comput. Syst. Sci. 75(3): 163-177 (2009) |
| 106 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Determination of finite automata accepting subregular languages.
Theor. Comput. Sci. 410(35): 3209-3222 (2009) |
| 105 | | Hermann Gruber,
Markus Holzer:
Language operations with regular expressions of polynomial size.
Theor. Comput. Sci. 410(35): 3281-3289 (2009) |
| 104 | | Franziska Biegler,
Mark Daley,
Markus Holzer,
Ian McQuillan:
On the uniqueness of shuffle on words and finite languages.
Theor. Comput. Sci. 410(38-40): 3711-3724 (2009) |
| 2008 |
|---|
| 103 | | Markus Holzer,
Martin Kutrib:
Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity.
CIAA 2008: 1-16 |
| 102 | | Markus Holzer,
Martin Kutrib,
Andreas Malcher:
Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
CSP 2008: 93-107 |
| 101 | | Hermann Gruber,
Markus Holzer:
Provably Shorter Regular Expressions from Deterministic Finite Automata.
Developments in Language Theory 2008: 383-395 |
| 100 | | Hermann Gruber,
Markus Holzer:
Finite Automata, Digraph Connectivity, and Regular Expression Size.
ICALP (2) 2008: 39-50 |
| 99 | | Suna Bensch,
Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Deterministic Input-Reversal and Input-Revolving Finite Automata.
LATA 2008: 113-124 |
| 98 | | Henning Bordihn,
Markus Holzer:
Random Context in Regulated Rewriting VersusCooperating Distributed Grammar Systems.
LATA 2008: 125-136 |
| 97 | | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
Equilibria of Graphical Games with Symmetries.
WINE 2008: 198-209 |
| 96 | | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
On Iterated Dominance, Matrix Elimination, and Matched Paths.
Electronic Colloquium on Computational Complexity (ECCC) 15(077): (2008) |
| 95 | | Henning Bordihn,
Markus Holzer:
A note on cooperating distributed grammar systems working in combined modes.
Inf. Process. Lett. 108(1): 10-14 (2008) |
| 2007 |
|---|
| 94 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Hairpin Finite Automata.
Developments in Language Theory 2007: 108-119 |
| 93 | | Hermann Gruber,
Markus Holzer:
Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.
Developments in Language Theory 2007: 205-216 |
| 92 | | Hermann Gruber,
Markus Holzer,
Oliver Ruepp:
Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms.
FUN 2007: 183-197 |
| 91 | | Markus Holzer,
Oliver Ruepp:
The Troubles of Interior Design-A Complexity Analysis of the Game Heyawake.
FUN 2007: 198-212 |
| 90 | | Hermann Gruber,
Markus Holzer,
Martin Kutrib:
More on the Size of Higman-Haines Sets: Effective Constructions.
MCU 2007: 193-204 |
| 89 | | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
Symmetries and the Complexity of Pure Nash Equilibrium.
STACS 2007: 212-223 |
| 88 | | Martin Beaudry,
Markus Holzer:
The Complexity of Tensor Circuit Evaluation.
Computational Complexity 16(1): 60-111 (2007) |
| 87 | | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
Equilibria of Graphical Games with Symmetries.
Electronic Colloquium on Computational Complexity (ECCC) 14(136): (2007) |
| 86 | | Henning Bordihn,
Markus Holzer:
Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited.
Fundam. Inform. 76(3): 255-270 (2007) |
| 85 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Hybrid Extended Finite Automata.
Int. J. Found. Comput. Sci. 18(4): 745-760 (2007) |
| 84 | | Maurice H. ter Beek,
Erzsébet Csuhaj-Varjú,
György Vaszil,
Markus Holzer:
On Competence in CD Grammar Systems with Parallel Rewriting.
Int. J. Found. Comput. Sci. 18(6): 1425-1439 (2007) |
| 83 |  | Markus Holzer,
Martin Kutrib,
Jens Reimann:
Non-Recursive Trade-Offs for Deterministic Restarting Automata.
Journal of Automata, Languages and Combinatorics 12(1-2): 195-213 (2007) |
| 82 | | Hermann Gruber,
Markus Holzer:
On the average state and transition complexity of finite languages.
Theor. Comput. Sci. 387(2): 155-166 (2007) |
| 81 | | Hermann Gruber,
Markus Holzer,
Martin Kutrib:
The size of Higman-Haines sets.
Theor. Comput. Sci. 387(2): 167-176 (2007) |
| 2006 |
|---|
| 80 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Hybrid Extended Finite Automata.
CIAA 2006: 34-45 |
| 79 | | Hermann Gruber,
Markus Holzer:
Finding Lower Bounds for Nondeterministic State Complexity Is Hard.
Developments in Language Theory 2006: 363-374 |
| 78 | | Henning Bordihn,
Markus Holzer:
Programmed grammars and their relation to the LBA problem.
Acta Inf. 43(4): 223-242 (2006) |
| 77 | | Hermann Gruber,
Markus Holzer:
Finding Lower Bounds for Nondeterministic State Complexity is Hard.
Electronic Colloquium on Computational Complexity (ECCC) 13(027): (2006) |
| 76 | | Felix Brandt,
Felix A. Fischer,
Markus Holzer:
Symmetries and the Complexity of Pure Nash Equilibrium.
Electronic Colloquium on Computational Complexity (ECCC) 13(091): (2006) |
| 75 | | Markus Holzer,
Martin Kutrib:
Variable Complexity of Simple Programs.
Fundam. Inform. 74(4): 511-528 (2006) |
| 74 | | Felix A. Fischer,
Markus Holzer,
Stefan Katzenbeisser:
The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria.
Inf. Process. Lett. 99(6): 239-245 (2006) |
| 73 | | Erzsébet Csuhaj-Varjú,
Jürgen Dassow,
Markus Holzer:
CD grammar systems with competence based entry conditions in their cooperation protocols.
Int. J. Comput. Math. 83(2): 159-169 (2006) |
| 72 | | Henning Bordihn,
Henning Fernau,
Markus Holzer,
Vincenzo Manca,
Carlos Martín-Vide:
Iterated sequential transducers as language generating devices.
Theor. Comput. Sci. 369(1-3): 67-81 (2006) |
| 2005 |
|---|
| 71 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Revolving-Input Finite Automata.
Developments in Language Theory 2005: 168-179 |
| 70 | | Hermann Gruber,
Markus Holzer,
Astrid Kiehn,
Barbara König:
On Timed Automata with Discrete Time - Structural and Language Theoretical Characterization.
Developments in Language Theory 2005: 272-283 |
| 69 | | Markus Holzer,
Friedrich Otto:
Shrinking Multi-pushdown Automata.
FCT 2005: 305-316 |
| 68 | | Henning Fernau,
Rudolf Freund,
Markus Holzer:
Representations of Recursively Enumerable Array Languages by Contextual Array Grammars.
Fundam. Inform. 64(1-4): 159-170 (2005) |
| 67 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Unsolvability levels of operation problems for subclasses of context-free languages.
Int. J. Found. Comput. Sci. 16(3): 423-440 (2005) |
| 66 | | Jürgen Dassow,
Markus Holzer:
Language families defined by a ciliate bio-operation: hierarchies and decision problems.
Int. J. Found. Comput. Sci. 16(4): 645-662 (2005) |
| 65 | | Markus Holzer,
Martin Kutrib:
On the descriptional complexity of finite automata with modified acceptance conditions.
Theor. Comput. Sci. 330(2): 267-285 (2005) |
| 64 | | Martin Beaudry,
José M. Fernandez,
Markus Holzer:
A common algebraic description for probabilistic and quantum computations, .
Theor. Comput. Sci. 345(2-3): 206-234 (2005) |
| 2004 |
|---|
| 63 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages.
CIAA 2004: 68-79 |
| 62 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages.
Developments in Language Theory 2004: 102-113 |
| 61 | | Maurice H. ter Beek,
Erzsébet Csuhaj-Varjú,
Markus Holzer,
György Vaszil:
On Competence in CD Grammar Systems.
Developments in Language Theory 2004: 76-88 |
| 60 | | Markus Holzer,
Martin Kutrib:
Register Complexity of LOOP-, WHILE-, and GOTO-Programs.
MCU 2004: 233-244 |
| 59 | | Martin Beaudry,
José M. Fernandez,
Markus Holzer:
A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract).
MFCS 2004: 851-862 |
| 58 | | Markus Holzer,
Stefan Katzenbeisser,
Christian Schallhart:
Towards Formal Semantics for ODRL.
ODRL Workshop 2004: 137-148 |
| 57 | | Markus Holzer,
Barbara König:
Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other (Column: Formal Language Theory).
Bulletin of the EATCS 83: 139-155 (2004) |
| 56 | | Markus Holzer,
Waltraud Holzer:
TantrixTM rotation puzzles are intractable.
Discrete Applied Mathematics 144(3): 345-358 (2004) |
| 55 | | Henning Bordihn,
Markus Holzer,
Martin Kutrib:
Economy of Description for Basic Constructions on Rational Transductions.
Journal of Automata, Languages and Combinatorics 9(2/3): 175-188 (2004) |
| 54 | | Markus Holzer,
Stefan Schwoon:
Assembling molecules in ATOMIX is hard.
Theor. Comput. Sci. 303(3): 447-462 (2004) |
| 53 | | Markus Holzer,
Barbara König:
On deterministic finite automata and syntactic monoid size.
Theor. Comput. Sci. 327(3): 319-347 (2004) |
| 2003 |
|---|
| 52 | | Markus Holzer,
Barbara König:
On Deterministic Finite Automata and Syntactic Monoid Size, Continued.
Developments in Language Theory 2003: 349-360 |
| 51 | | Markus Holzer,
Martin Kutrib:
Flip-Pushdown Automata: Nondeterminism Is Better than Determinism.
Developments in Language Theory 2003: 361-372 |
| 50 | | Henning Bordihn,
Henning Fernau,
Markus Holzer:
On Iterated Sequential Transducers.
Grammars and Automata for String Processing 2003: 121-130 |
| 49 | | Markus Holzer,
Martin Kutrib:
Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k.
ICALP 2003: 490-501 |
| 48 | | Markus Holzer,
Martin Kutrib:
Nondeterministic Descriptional Complexity Of Regular Languages.
Int. J. Found. Comput. Sci. 14(6): 1087-1102 (2003) |
| 47 | | Markus Holzer,
Pierre McKenzie:
Alternating and empty alternating auxiliary stack automata.
Theor. Comput. Sci. 1-3(299): 307-326 (2003) |
| 46 | | Henning Fernau,
Markus Holzer,
Rudolf Freund:
Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes le k and =k.
Theor. Comput. Sci. 1-3(299): 633-662 (2003) |
| 45 | | Martin Beaudry,
Markus Holzer,
Gundula Niemann,
Friedrich Otto:
McNaughton families of languages.
Theor. Comput. Sci. 290(3): 1581-1628 (2003) |
| 2002 |
|---|
| 44 | | Markus Holzer,
Martin Kutrib:
State Complexity of Basic Operations on Nondeterministic Finite Automata.
CIAA 2002: 148-157 |
| 43 | | Markus Holzer,
Martin Kutrib:
Unary Language Operations and Their Nondeterministic State Complexity.
Developments in Language Theory 2002: 162-172 |
| 42 | | Markus Holzer,
Barbara König:
On Deterministic Finite Automata and Syntactic Monoid Size.
Developments in Language Theory 2002: 258-269 |
| 41 | | Carsten Damm,
Markus Holzer,
Pierre McKenzie:
The complexity of tensor calculus.
Computational Complexity 11(1-2): 54-89 (2002) |
| 40 | | Henning Bordihn,
Markus Holzer:
On the Computational Complexity of Synchronized Context-Free Languages.
J. UCS 8(2): 119-140 (2002) |
| 39 | | Henning Fernau,
Markus Holzer:
Graph-Controlled Cooperating Distributed Grammar Systems with Singleton Components.
Journal of Automata, Languages and Combinatorics 7(4): 487-503 (2002) |
| 38 | | Markus Holzer:
Multi-head finite automata: data-independent versus data-dependent computations.
Theor. Comput. Sci. 286(1): 97-116 (2002) |
| 2001 |
|---|
| 37 | | Markus Holzer,
Martin Kutrib:
Improving Raster Image Run-Length Encoding Using Data Order.
CIAA 2001: 161-176 |
| 36 | | Martin Beaudry,
Markus Holzer,
Gundula Niemann,
Friedrich Otto:
On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy.
Developments in Language Theory 2001: 340-348 |
| 35 | | Martin Beaudry,
Markus Holzer:
The Complexity of Tensor Circuit Evaluation.
MFCS 2001: 173-185 |
| 34 | | Henning Bordihn,
Markus Holzer:
On the Number of Active Symbols in L and CD Grammar Systems.
Journal of Automata, Languages and Combinatorics 6(4): 411-426 (2001) |
| 33 | | Markus Holzer,
Kai Salomaa,
Sheng Yu:
On the State Complexity of k-Entry Deterministic Finite Automata.
Journal of Automata, Languages and Combinatorics 6(4): 453-466 (2001) |
| 32 | | Henning Fernau,
Markus Holzer,
Rudolf Freund:
Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization.
Theor. Comput. Sci. 259(1-2): 405-426 (2001) |
| 2000 |
|---|
| 31 | | Carsten Damm,
Markus Holzer,
Pierre McKenzie:
The Complexity of Tensor Calculus.
IEEE Conference on Computational Complexity 2000: 70-86 |
| 30 | | Markus Holzer,
Pierre McKenzie:
Alternating and Empty Alternating Auxiliary Stack Automata.
MFCS 2000: 415-425 |
| 29 | | Henning Fernau,
Markus Holzer:
External Contextual and Conditional Languages.
Recent Topics in Mathematical and Computational Linguistics 2000: 104-120 |
| 28 | | Carsten Damm,
Markus Holzer,
Pierre McKenzie:
The Complexity of Tensor Calculus
Electronic Colloquium on Computational Complexity (ECCC) 7(36): (2000) |
| 27 | | Henning Bordihn,
Markus Holzer:
Grammar Systems with Negated Conditions in their Cooperation Protocols
J. UCS 6(12): 1165-1184 (2000) |
| 1999 |
|---|
| 26 | | Henning Bordihn,
Markus Holzer:
Cooperating distributed grammar systems with non-terminating components.
Developments in Language Theory 1999: 305-315 |
| 25 | | Markus Holzer:
On fixed and general membership for external and internal contextual languages.
Developments in Language Theory 1999: 351-361 |
| 24 | | Henning Fernau,
Rudolf Freund,
Markus Holzer:
Regulated Array Grammars of Finite Index. Part I: Theoretical Investigations.
Grammatical Models of Multi-Agent Systems 1999: 157-181 |
| 23 | | Henning Fernau,
Rudolf Freund,
Markus Holzer:
Regulated Array Grammars of Finite Index. Part II: Syntactic Pattern Recognition.
Grammatical Models of Multi-Agent Systems 1999: 284-296 |
| 22 | | Henning Bordihn,
Henning Fernau,
Markus Holzer:
On Accepting Pure Lindenmayer Systems.
Fundam. Inform. 38(4): 365-375 (1999) |
| 21 | | Henning Bordihn,
Markus Holzer:
On a Hierarchy of Languages Generated by Cooperating Distributed Grammar Systems.
Inf. Process. Lett. 69(2): 59-62 (1999) |
| 1998 |
|---|
| 20 | | Markus Holzer,
Muriel Quenzer:
VisA: towards a students' green card to automata theory and formal languages.
ACSE 1998: 67-75 |
| 19 | | Markus Holzer,
Muriel Quenzer:
VisA: A Tool for Visualizing and Animating Automata and Formal Languages.
Graph Drawing 1998: 450-451 |
| 18 | | Henning Fernau,
Rudolf Freund,
Markus Holzer:
The Generative Power of d-Dimensional #-Context-Free Array Grammars.
MCU (2) 1998: 43-56 |
| 17 | | Henning Fernau,
Rudolf Freund,
Markus Holzer:
Character Recognition with k-Head Finite Array Automata.
SSPR/SPR 1998: 282-291 |
| 1997 |
|---|
| 16 | | Henning Fernau,
Markus Holzer,
Rudolf Freund:
Bounding resources in Cooperating Distributed Grammar Systems.
Developments in Language Theory 1997: 261-272 |
| 15 | | Markus Holzer:
Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations.
MFCS 1997: 299-308 |
| 14 | | Henning Fernau,
Markus Holzer:
Conditional Context-Free Languages of Finite Index.
New Trends in Formal Languages 1997: 10-26 |
| 13 | | Markus Holzer,
Klaus-Jörn Lange:
On the Complexity of Iterated Insertions.
New Trends in Formal Languages 1997: 440-453 |
| 12 | | Carsten Damm,
Markus Holzer,
Peter Rossmanith:
Expressing Uniformity via Oracles.
Theory Comput. Syst. 30(4): 355-366 (1997) |
| 1996 |
|---|
| 11 | | Henning Fernau,
Markus Holzer:
Accepting Multi-Agent Systems II.
Acta Cybern. 12(4): 361-380 (1996) |
| 10 | | Henning Fernau,
Markus Holzer,
Henning Bordihn:
Accepting Multi-Agent Systems.
Computers and Artificial Intelligence 15(2-3): (1996) |
| 9 | | Carsten Damm,
Markus Holzer:
Inductive Counting for Width-Restricted Branching Programs.
Inf. Comput. 130(1): 91-99 (1996) |
| 1995 |
|---|
| 8 | | Markus Holzer:
On Emptiness and Counting for Alternating Finite Automata.
Developments in Language Theory 1995: 88-97 |
| 7 | | Carsten Damm,
Markus Holzer:
Automata That Take Advice.
MFCS 1995: 149-158 |
| 6 | | Carsten Damm,
Markus Holzer,
Peter Rossmanith:
Expressing Uniformity via Oracles
Universität Trier, Mathematik/Informatik, Forschungsbericht 95-01: (1995) |
| 1994 |
|---|
| 5 | | Carsten Damm,
Markus Holzer:
Inductive Counting Below LOGSPACE.
MFCS 1994: 276-285 |
| 4 | | Carsten Damm,
Markus Holzer:
Inductive Counting below LOGSPACE
Universität Trier, Mathematik/Informatik, Forschungsbericht 94-12: (1994) |
| 1993 |
|---|
| 3 | | Carsten Damm,
Markus Holzer,
Klaus-Jörn Lange,
Peter Rossmanith:
Deterministic OL Languages are of Very Low Complexity: DOL is in AC0.
Developments in Language Theory 1993: 305-313 |
| 2 | | Markus Holzer,
Klaus-Jörn Lange:
On the Complexities of Linear LL(1) and LR(1) Grammars.
FCT 1993: 299-308 |
| 1992 |
|---|
| 1 | | Carsten Damm,
Markus Holzer,
Klaus-Jörn Lange:
Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers.
MFCS 1992: 227-235 |
