dblp.uni-trier.dewww.uni-trier.de

Markus Holzer Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
116EEHermann Gruber, Markus Holzer, Michael Tautschnig: Short Regular Expressions from Finite Automata: Empirical Results. CIAA 2009: 188-197
115EEMarkus Holzer, Andreas Maletti: An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton. CIAA 2009: 4-13
114EEHermann Gruber, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287
113EEMarkus Holzer, Martin Kutrib: Descriptional and Computational Complexity of Finite Automata. LATA 2009: 23-42
112EEHenning Bordihn, Markus Holzer, Martin Kutrib: Undecidability of Operation Problems for T0L Languages and Subclasses. LATA 2009: 236-246
111EEHermann Gruber, Markus Holzer, Martin Kutrib: On Measuring Non-Recursive Trade-Offs CoRR abs/0907.5063: (2009)
110EEHermann Gruber, Markus Holzer, Martin Kutrib: More on the Size of Higman-Haines Sets: Effective Constructions. Fundam. Inform. 91(1): 105-121 (2009)
109EESuna Bensch, Henning Bordihn, Markus Holzer, Martin Kutrib: On input-revolving deterministic and nondeterministic finite automata. Inf. Comput. 207(11): 1140-1155 (2009)
108EEMarkus Holzer, Martin Kutrib: Nondeterministic Finite Automata - Recent Results on the Descriptional and Computational Complexity. Int. J. Found. Comput. Sci. 20(4): 563-580 (2009)
107EEFelix Brandt, Felix A. Fischer, Markus Holzer: Symmetries and the complexity of pure Nash equilibrium. J. Comput. Syst. Sci. 75(3): 163-177 (2009)
106EEHenning Bordihn, Markus Holzer, Martin Kutrib: Determination of finite automata accepting subregular languages. Theor. Comput. Sci. 410(35): 3209-3222 (2009)
105EEHermann Gruber, Markus Holzer: Language operations with regular expressions of polynomial size. Theor. Comput. Sci. 410(35): 3281-3289 (2009)
104EEFranziska 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
103EEMarkus Holzer, Martin Kutrib: Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity. CIAA 2008: 1-16
102EEMarkus Holzer, Martin Kutrib, Andreas Malcher: Multi-Head Finite Automata: Characterizations, Concepts and Open Problems CSP 2008: 93-107
101EEHermann Gruber, Markus Holzer: Provably Shorter Regular Expressions from Deterministic Finite Automata. Developments in Language Theory 2008: 383-395
100EEHermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50
99EESuna Bensch, Henning Bordihn, Markus Holzer, Martin Kutrib: Deterministic Input-Reversal and Input-Revolving Finite Automata. LATA 2008: 113-124
98EEHenning Bordihn, Markus Holzer: Random Context in Regulated Rewriting VersusCooperating Distributed Grammar Systems. LATA 2008: 125-136
97EEFelix Brandt, Felix A. Fischer, Markus Holzer: Equilibria of Graphical Games with Symmetries. WINE 2008: 198-209
96EEFelix Brandt, Felix A. Fischer, Markus Holzer: On Iterated Dominance, Matrix Elimination, and Matched Paths. Electronic Colloquium on Computational Complexity (ECCC) 15(077): (2008)
95EEHenning Bordihn, Markus Holzer: A note on cooperating distributed grammar systems working in combined modes. Inf. Process. Lett. 108(1): 10-14 (2008)
2007
94EEHenning Bordihn, Markus Holzer, Martin Kutrib: Hairpin Finite Automata. Developments in Language Theory 2007: 108-119
93EEHermann Gruber, Markus Holzer: Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP. Developments in Language Theory 2007: 205-216
92EEHermann Gruber, Markus Holzer, Oliver Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. FUN 2007: 183-197
91EEMarkus Holzer, Oliver Ruepp: The Troubles of Interior Design-A Complexity Analysis of the Game Heyawake. FUN 2007: 198-212
90EEHermann Gruber, Markus Holzer, Martin Kutrib: More on the Size of Higman-Haines Sets: Effective Constructions. MCU 2007: 193-204
89EEFelix Brandt, Felix A. Fischer, Markus Holzer: Symmetries and the Complexity of Pure Nash Equilibrium. STACS 2007: 212-223
88EEMartin Beaudry, Markus Holzer: The Complexity of Tensor Circuit Evaluation. Computational Complexity 16(1): 60-111 (2007)
87EEFelix Brandt, Felix A. Fischer, Markus Holzer: Equilibria of Graphical Games with Symmetries. Electronic Colloquium on Computational Complexity (ECCC) 14(136): (2007)
86EEHenning Bordihn, Markus Holzer: Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited. Fundam. Inform. 76(3): 255-270 (2007)
85EEHenning Bordihn, Markus Holzer, Martin Kutrib: Hybrid Extended Finite Automata. Int. J. Found. Comput. Sci. 18(4): 745-760 (2007)
84EEMaurice 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)
82EEHermann Gruber, Markus Holzer: On the average state and transition complexity of finite languages. Theor. Comput. Sci. 387(2): 155-166 (2007)
81EEHermann Gruber, Markus Holzer, Martin Kutrib: The size of Higman-Haines sets. Theor. Comput. Sci. 387(2): 167-176 (2007)
2006
80EEHenning Bordihn, Markus Holzer, Martin Kutrib: Hybrid Extended Finite Automata. CIAA 2006: 34-45
79EEHermann Gruber, Markus Holzer: Finding Lower Bounds for Nondeterministic State Complexity Is Hard. Developments in Language Theory 2006: 363-374
78EEHenning Bordihn, Markus Holzer: Programmed grammars and their relation to the LBA problem. Acta Inf. 43(4): 223-242 (2006)
77EEHermann Gruber, Markus Holzer: Finding Lower Bounds for Nondeterministic State Complexity is Hard. Electronic Colloquium on Computational Complexity (ECCC) 13(027): (2006)
76EEFelix Brandt, Felix A. Fischer, Markus Holzer: Symmetries and the Complexity of Pure Nash Equilibrium. Electronic Colloquium on Computational Complexity (ECCC) 13(091): (2006)
75EEMarkus Holzer, Martin Kutrib: Variable Complexity of Simple Programs. Fundam. Inform. 74(4): 511-528 (2006)
74EEFelix 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)
73EEErzsé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)
72EEHenning 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
71EEHenning Bordihn, Markus Holzer, Martin Kutrib: Revolving-Input Finite Automata. Developments in Language Theory 2005: 168-179
70EEHermann 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
69EEMarkus Holzer, Friedrich Otto: Shrinking Multi-pushdown Automata. FCT 2005: 305-316
68EEHenning Fernau, Rudolf Freund, Markus Holzer: Representations of Recursively Enumerable Array Languages by Contextual Array Grammars. Fundam. Inform. 64(1-4): 159-170 (2005)
67EEHenning 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)
66EEJü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)
65EEMarkus Holzer, Martin Kutrib: On the descriptional complexity of finite automata with modified acceptance conditions. Theor. Comput. Sci. 330(2): 267-285 (2005)
64EEMartin 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
63EEHenning Bordihn, Markus Holzer, Martin Kutrib: Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages. CIAA 2004: 68-79
62EEHenning 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
61EEMaurice 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
60EEMarkus Holzer, Martin Kutrib: Register Complexity of LOOP-, WHILE-, and GOTO-Programs. MCU 2004: 233-244
59EEMartin Beaudry, José M. Fernandez, Markus Holzer: A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract). MFCS 2004: 851-862
58EEMarkus 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)
56EEMarkus 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)
54EEMarkus Holzer, Stefan Schwoon: Assembling molecules in ATOMIX is hard. Theor. Comput. Sci. 303(3): 447-462 (2004)
53EEMarkus Holzer, Barbara König: On deterministic finite automata and syntactic monoid size. Theor. Comput. Sci. 327(3): 319-347 (2004)
2003
52EEMarkus Holzer, Barbara König: On Deterministic Finite Automata and Syntactic Monoid Size, Continued. Developments in Language Theory 2003: 349-360
51EEMarkus 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
49EEMarkus Holzer, Martin Kutrib: Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k. ICALP 2003: 490-501
48EEMarkus Holzer, Martin Kutrib: Nondeterministic Descriptional Complexity Of Regular Languages. Int. J. Found. Comput. Sci. 14(6): 1087-1102 (2003)
47EEMarkus Holzer, Pierre McKenzie: Alternating and empty alternating auxiliary stack automata. Theor. Comput. Sci. 1-3(299): 307-326 (2003)
46EEHenning 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
44EEMarkus Holzer, Martin Kutrib: State Complexity of Basic Operations on Nondeterministic Finite Automata. CIAA 2002: 148-157
43EEMarkus Holzer, Martin Kutrib: Unary Language Operations and Their Nondeterministic State Complexity. Developments in Language Theory 2002: 162-172
42EEMarkus Holzer, Barbara König: On Deterministic Finite Automata and Syntactic Monoid Size. Developments in Language Theory 2002: 258-269
41EECarsten Damm, Markus Holzer, Pierre McKenzie: The complexity of tensor calculus. Computational Complexity 11(1-2): 54-89 (2002)
40EEHenning 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)
38EEMarkus Holzer: Multi-head finite automata: data-independent versus data-dependent computations. Theor. Comput. Sci. 286(1): 97-116 (2002)
2001
37EEMarkus Holzer, Martin Kutrib: Improving Raster Image Run-Length Encoding Using Data Order. CIAA 2001: 161-176
36EEMartin 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
35EEMartin 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)
32EEHenning 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
31EECarsten Damm, Markus Holzer, Pierre McKenzie: The Complexity of Tensor Calculus. IEEE Conference on Computational Complexity 2000: 70-86
30EEMarkus 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
28EECarsten Damm, Markus Holzer, Pierre McKenzie: The Complexity of Tensor Calculus Electronic Colloquium on Computational Complexity (ECCC) 7(36): (2000)
27EEHenning 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)
21EEHenning Bordihn, Markus Holzer: On a Hierarchy of Languages Generated by Cooperating Distributed Grammar Systems. Inf. Process. Lett. 69(2): 59-62 (1999)
1998
20EEMarkus Holzer, Muriel Quenzer: VisA: towards a students' green card to automata theory and formal languages. ACSE 1998: 67-75
19EEMarkus 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
15EEMarkus 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
11EEHenning 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
7EECarsten 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
5EECarsten 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
1EECarsten Damm, Markus Holzer, Klaus-Jörn Lange: Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers. MFCS 1992: 227-235

Coauthor Index

1Martin Beaudry [35] [36] [45] [59] [64] [88]
2Maurice H. ter Beek [61] [84]
3Suna Bensch [99] [109]
4Franziska Biegler [104]
5Henning Bordihn [10] [21] [22] [26] [27] [34] [40] [50] [55] [62] [63] [67] [71] [72] [78] [80] [85] [86] [94] [95] [98] [99] [106] [109] [112]
6Felix Brandt [76] [87] [89] [96] [97] [107]
7Erzsébet Csuhaj-Varjú [61] [73] [84]
8Mark Daley [104]
9Carsten Damm [1] [3] [4] [5] [6] [7] [9] [12] [28] [31] [41]
10Jürgen Dassow [66] [73]
11José M. Fernandez [59] [64]
12Henning Fernau [10] [11] [14] [16] [17] [18] [22] [23] [24] [29] [32] [39] [46] [50] [68] [72]
13Felix A. Fischer [74] [76] [87] [89] [96] [97] [107]
14Rudolf Freund [16] [17] [18] [23] [24] [32] [46] [68]
15Hermann Gruber [70] [77] [79] [81] [82] [90] [92] [93] [100] [101] [105] [110] [111] [114] [116]
16Waltraud Holzer [56]
17Stefan Katzenbeisser [58] [74]
18Astrid Kiehn [70]
19Barbara König [42] [52] [53] [57] [70]
20Martin Kutrib [37] [43] [44] [48] [49] [51] [55] [60] [62] [63] [65] [67] [71] [75] [80] [81] [83] [85] [90] [94] [99] [102] [103] [106] [108] [109] [110] [111] [112] [113]
21Klaus-Jörn Lange [1] [2] [3] [13]
22Andreas Malcher [102]
23Andreas Maletti [115]
24Vincenzo Manca [72]
25Carlos Martín-Vide [72]
26Pierre McKenzie [28] [30] [31] [41] [47]
27Ian McQuillan [104]
28Gundula Niemann [36] [45]
29Friedrich Otto [36] [45] [69]
30Muriel Quenzer [19] [20]
31Jens Reimann [83]
32Peter Rossmanith [3] [6] [12]
33Oliver Ruepp [91] [92]
34Kai Salomaa [33]
35Christian Schallhart [58]
36Stefan Schwoon [54]
37Michael Tautschnig [116]
38György Vaszil [61] [84]
39Sheng Yu [33]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)