2009 | ||
---|---|---|
107 | EE | Markus Holzer, Martin Kutrib: Descriptional and Computational Complexity of Finite Automata. LATA 2009: 23-42 |
106 | EE | Henning Bordihn, Markus Holzer, Martin Kutrib: Undecidability of Operation Problems for T0L Languages and Subclasses. LATA 2009: 236-246 |
105 | EE | Hermann Gruber, Markus Holzer, Martin Kutrib: More on the Size of Higman-Haines Sets: Effective Constructions. Fundam. Inform. 91(1): 105-121 (2009) |
104 | EE | Felix Brandt, Felix Fischer, Markus Holzer: Symmetries and the complexity of pure Nash equilibrium. J. Comput. Syst. Sci. 75(3): 163-177 (2009) |
2008 | ||
103 | EE | 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: 117-136 | |
101 | EE | Hermann Gruber, Markus Holzer: Provably Shorter Regular Expressions from Deterministic Finite Automata. Developments in Language Theory 2008: 383-395 |
100 | EE | Hermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50 |
99 | EE | Suna Bensch, Henning Bordihn, Markus Holzer, Martin Kutrib: Deterministic Input-Reversal and Input-Revolving Finite Automata. LATA 2008: 113-124 |
98 | EE | Henning Bordihn, Markus Holzer: Random Context in Regulated Rewriting VersusCooperating Distributed Grammar Systems. LATA 2008: 125-136 |
97 | EE | Felix Brandt, Felix A. Fischer, Markus Holzer: Equilibria of Graphical Games with Symmetries. WINE 2008: 198-209 |
96 | EE | 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 | EE | 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 | EE | Henning Bordihn, Markus Holzer, Martin Kutrib: Hairpin Finite Automata. Developments in Language Theory 2007: 108-119 |
93 | EE | Hermann Gruber, Markus Holzer: Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP. Developments in Language Theory 2007: 205-216 |
92 | EE | Hermann Gruber, Markus Holzer, Oliver Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. FUN 2007: 183-197 |
91 | EE | Markus Holzer, Oliver Ruepp: The Troubles of Interior Design-A Complexity Analysis of the Game Heyawake. FUN 2007: 198-212 |
90 | EE | Hermann Gruber, Markus Holzer, Martin Kutrib: More on the Size of Higman-Haines Sets: Effective Constructions. MCU 2007: 193-204 |
89 | EE | Felix Brandt, Felix A. Fischer, Markus Holzer: Symmetries and the Complexity of Pure Nash Equilibrium. STACS 2007: 212-223 |
88 | EE | Martin Beaudry, Markus Holzer: The Complexity of Tensor Circuit Evaluation. Computational Complexity 16(1): 60-111 (2007) |
87 | EE | Felix Brandt, Felix A. Fischer, Markus Holzer: Equilibria of Graphical Games with Symmetries. Electronic Colloquium on Computational Complexity (ECCC) 14(136): (2007) |
86 | EE | Henning Bordihn, Markus Holzer: Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited. Fundam. Inform. 76(3): 255-270 (2007) |
85 | EE | Henning Bordihn, Markus Holzer, Martin Kutrib: Hybrid Extended Finite Automata. Int. J. Found. Comput. Sci. 18(4): 745-760 (2007) |
84 | EE | 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 | EE | Hermann Gruber, Markus Holzer: On the average state and transition complexity of finite languages. Theor. Comput. Sci. 387(2): 155-166 (2007) |
81 | EE | Hermann Gruber, Markus Holzer, Martin Kutrib: The size of Higman-Haines sets. Theor. Comput. Sci. 387(2): 167-176 (2007) |
2006 | ||
80 | EE | Henning Bordihn, Markus Holzer, Martin Kutrib: Hybrid Extended Finite Automata. CIAA 2006: 34-45 |
79 | EE | Hermann Gruber, Markus Holzer: Finding Lower Bounds for Nondeterministic State Complexity Is Hard. Developments in Language Theory 2006: 363-374 |
78 | EE | Henning Bordihn, Markus Holzer: Programmed grammars and their relation to the LBA problem. Acta Inf. 43(4): 223-242 (2006) |
77 | EE | Hermann Gruber, Markus Holzer: Finding Lower Bounds for Nondeterministic State Complexity is Hard. Electronic Colloquium on Computational Complexity (ECCC) 13(027): (2006) |
76 | EE | 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 | EE | Markus Holzer, Martin Kutrib: Variable Complexity of Simple Programs. Fundam. Inform. 74(4): 511-528 (2006) |
74 | EE | 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 | EE | 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 | EE | 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 | EE | Henning Bordihn, Markus Holzer, Martin Kutrib: Revolving-Input Finite Automata. Developments in Language Theory 2005: 168-179 |
70 | EE | 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 | EE | Markus Holzer, Friedrich Otto: Shrinking Multi-pushdown Automata. FCT 2005: 305-316 |
68 | EE | 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 | EE | 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 | EE | 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 | EE | Markus Holzer, Martin Kutrib: On the descriptional complexity of finite automata with modified acceptance conditions. Theor. Comput. Sci. 330(2): 267-285 (2005) |
64 | EE | 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 | EE | Henning Bordihn, Markus Holzer, Martin Kutrib: Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages. CIAA 2004: 68-79 |
62 | EE | 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 | EE | 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 | EE | Markus Holzer, Martin Kutrib: Register Complexity of LOOP-, WHILE-, and GOTO-Programs. MCU 2004: 233-244 |
59 | EE | Martin Beaudry, José M. Fernandez, Markus Holzer: A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract). MFCS 2004: 851-862 |
58 | EE | 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 | EE | 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 | EE | Markus Holzer, Stefan Schwoon: Assembling molecules in ATOMIX is hard. Theor. Comput. Sci. 303(3): 447-462 (2004) |
53 | EE | Markus Holzer, Barbara König: On deterministic finite automata and syntactic monoid size. Theor. Comput. Sci. 327(3): 319-347 (2004) |
2003 | ||
52 | EE | Markus Holzer, Barbara König: On Deterministic Finite Automata and Syntactic Monoid Size, Continued. Developments in Language Theory 2003: 349-360 |
51 | EE | 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 | EE | Markus Holzer, Martin Kutrib: Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k. ICALP 2003: 490-501 |
48 | EE | Markus Holzer, Martin Kutrib: Nondeterministic Descriptional Complexity Of Regular Languages. Int. J. Found. Comput. Sci. 14(6): 1087-1102 (2003) |
47 | EE | Markus Holzer, Pierre McKenzie: Alternating and empty alternating auxiliary stack automata. Theor. Comput. Sci. 1-3(299): 307-326 (2003) |
46 | EE | 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 | EE | Markus Holzer, Martin Kutrib: State Complexity of Basic Operations on Nondeterministic Finite Automata. CIAA 2002: 148-157 |
43 | EE | Markus Holzer, Martin Kutrib: Unary Language Operations and Their Nondeterministic State Complexity. Developments in Language Theory 2002: 162-172 |
42 | EE | Markus Holzer, Barbara König: On Deterministic Finite Automata and Syntactic Monoid Size. Developments in Language Theory 2002: 258-269 |
41 | EE | Carsten Damm, Markus Holzer, Pierre McKenzie: The complexity of tensor calculus. Computational Complexity 11(1-2): 54-89 (2002) |
40 | EE | 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 | EE | Markus Holzer: Multi-head finite automata: data-independent versus data-dependent computations. Theor. Comput. Sci. 286(1): 97-116 (2002) |
2001 | ||
37 | EE | Markus Holzer, Martin Kutrib: Improving Raster Image Run-Length Encoding Using Data Order. CIAA 2001: 161-176 |
36 | EE | 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 | EE | 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 | EE | 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 | EE | Carsten Damm, Markus Holzer, Pierre McKenzie: The Complexity of Tensor Calculus. IEEE Conference on Computational Complexity 2000: 70-86 |
30 | EE | 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 | EE | Carsten Damm, Markus Holzer, Pierre McKenzie: The Complexity of Tensor Calculus Electronic Colloquium on Computational Complexity (ECCC) 7(36): (2000) |
27 | EE | 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 | EE | 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 | EE | Markus Holzer, Muriel Quenzer: VisA: towards a students' green card to automata theory and formal languages. ACSE 1998: 67-75 |
19 | EE | 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 | EE | 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 |