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

Martin Kutrib

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

2009
74EEMarkus Holzer, Martin Kutrib: Descriptional and Computational Complexity of Finite Automata. LATA 2009: 23-42
73EEHenning Bordihn, Markus Holzer, Martin Kutrib: Undecidability of Operation Problems for T0L Languages and Subclasses. LATA 2009: 236-246
72EEMartin Kutrib, Hartmut Messerschmidt, Friedrich Otto: On Stateless Deterministic Restarting Automata. SOFSEM 2009: 353-364
71EEHermann Gruber, Markus Holzer, Martin Kutrib: More on the Size of Higman-Haines Sets: Effective Constructions. Fundam. Inform. 91(1): 105-121 (2009)
2008
70EEMarkus Holzer, Martin Kutrib: Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity. CIAA 2008: 1-16
69 Markus Holzer, Martin Kutrib, Andreas Malcher: Multi-Head Finite Automata: Characterizations, Concepts and Open Problems. CSP 2008: 117-136
68EEHenning Bordihn, Martin Kutrib, Andreas Malcher: On the Computational Capacity of Parallel Communicating Finite Automata. Developments in Language Theory 2008: 146-157
67EESuna Bensch, Henning Bordihn, Markus Holzer, Martin Kutrib: Deterministic Input-Reversal and Input-Revolving Finite Automata. LATA 2008: 113-124
66EEMartin Kutrib, Andreas Malcher, Detlef Wotschke: The Boolean closure of linear context-free languages. Acta Inf. 45(3): 177-191 (2008)
65EEMartin Kutrib, Andreas Malcher: Fast reversible language recognition using cellular automata. Inf. Comput. 206(9-10): 1142-1151 (2008)
64EEMartin Kutrib, Jens Reimann: Succinct description of regular languages by weak restarting automata. Inf. Comput. 206(9-10): 1152-1160 (2008)
63EEMartin Kutrib, Jens Reimann: Optimal Simulations of Weak Restarting Automata. Int. J. Found. Comput. Sci. 19(4): 795-811 (2008)
2007
62EEMartin Kutrib, Andreas Malcher, Larissa Werlein: Regulated Nondeterminism in Pushdown Automata. CIAA 2007: 85-96
61EEHenning Bordihn, Markus Holzer, Martin Kutrib: Hairpin Finite Automata. Developments in Language Theory 2007: 108-119
60EEMartin Kutrib, Andreas Malcher: Real-Time Reversible Iterative Arrays. FCT 2007: 376-387
59EEHermann Gruber, Markus Holzer, Martin Kutrib: More on the Size of Higman-Haines Sets: Effective Constructions. MCU 2007: 193-204
58EEMartin Kutrib, Andreas Malcher: Finite turns and the regular closure of linear context-free languages. Discrete Applied Mathematics 155(16): 2152-2164 (2007)
57EEAndreas Klein, Martin Kutrib: Cellular Devices and Unary Languages. Fundam. Inform. 78(3): 343-368 (2007)
56EEHenning Bordihn, Markus Holzer, Martin Kutrib: Hybrid Extended Finite Automata. Int. J. Found. Comput. Sci. 18(4): 745-760 (2007)
55EEAndreas Klein, Martin Kutrib: Context-Free Grammars with Linked Nonterminals. Int. J. Found. Comput. Sci. 18(6): 1271-1282 (2007)
54EEMartin Kutrib, Andreas Malcher: When Church-Rosser Becomes Context Free. Int. J. Found. Comput. Sci. 18(6): 1293-1302 (2007)
53 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)
52EEMartin Kutrib, Andreas Malcher: Context-dependent nondeterminism for pushdown automata. Theor. Comput. Sci. 376(1-2): 101-111 (2007)
51EEHermann Gruber, Markus Holzer, Martin Kutrib: The size of Higman-Haines sets. Theor. Comput. Sci. 387(2): 167-176 (2007)
2006
50EEHenning Bordihn, Markus Holzer, Martin Kutrib: Hybrid Extended Finite Automata. CIAA 2006: 34-45
49EEMartin Kutrib, Andreas Malcher: Context-Dependent Nondeterminism for Pushdown Automata. Developments in Language Theory 2006: 133-144
48EEMartin Kutrib, Andreas Malcher: Fast Cellular Automata with Restricted Inter-Cell Communication: Computational Capacity. IFIP TCS 2006: 151-164
47EEMartin Kutrib, Andreas Malcher: Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability. MFCS 2006: 634-645
46EEMarkus Holzer, Martin Kutrib: Variable Complexity of Simple Programs. Fundam. Inform. 74(4): 511-528 (2006)
2005
45EEHenning Bordihn, Markus Holzer, Martin Kutrib: Revolving-Input Finite Automata. Developments in Language Theory 2005: 168-179
44EEHenning 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)
43EEMartin Kutrib: The phenomenon of non-recursive trade-offs. Int. J. Found. Comput. Sci. 16(5): 957-973 (2005)
42EEMarkus Holzer, Martin Kutrib: On the descriptional complexity of finite automata with modified acceptance conditions. Theor. Comput. Sci. 330(2): 267-285 (2005)
41EEMartin Kutrib: On the descriptional power of heads, counters, and pebbles. Theor. Comput. Sci. 330(2): 311-324 (2005)
2004
40EEHenning Bordihn, Markus Holzer, Martin Kutrib: Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages. CIAA 2004: 68-79
39EEHenning 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
38EEMartin Kutrib, Andreas Malcher, Detlef Wotschke: The Boolean Closure of Linear Context-Free Languages. Developments in Language Theory 2004: 284-295
37EEMarkus Holzer, Martin Kutrib: Register Complexity of LOOP-, WHILE-, and GOTO-Programs. MCU 2004: 233-244
36 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)
2003
35EEMarkus Holzer, Martin Kutrib: Flip-Pushdown Automata: Nondeterminism Is Better than Determinism. Developments in Language Theory 2003: 361-372
34EEMartin Kutrib: Dimension- and Time-Hierarchies for Small Time Bounds. FCT 2003: 321-332
33EEMarkus Holzer, Martin Kutrib: Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k. ICALP 2003: 490-501
32EEMartin Kutrib, Maurice Margenstern, Hiroshi Umeo: Foreword. Fundam. Inform. 58(2003): (2003)
31EEMartin Kutrib, Jan-Thomas Löwe: Space- and Time-Bounded Nondeterminism for Cellular Automata. Fundam. Inform. 58(2003): 273-293 (2003)
30EEMarkus Holzer, Martin Kutrib: Nondeterministic Descriptional Complexity Of Regular Languages. Int. J. Found. Comput. Sci. 14(6): 1087-1102 (2003)
29EEAndreas Klein, Martin Kutrib: Fast one-way cellular automata. Theor. Comput. Sci. 295: 233-250 (2003)
2002
28EEMarkus Holzer, Martin Kutrib: State Complexity of Basic Operations on Nondeterministic Finite Automata. CIAA 2002: 148-157
27EEAndreas Klein, Martin Kutrib: Self-Assembling Finite Automata. COCOON 2002: 310-319
26EEMarkus Holzer, Martin Kutrib: Unary Language Operations and Their Nondeterministic State Complexity. Developments in Language Theory 2002: 162-172
25EEMartin Kutrib, Jan-Thomas Löwe: String Transformation for n -Dimensional Image Compression. SOFSEM 2002: 208-217
24EEThomas Buchholz, Andreas Klein, Martin Kutrib: On Interacting Automata with Limited Nondeterminism. Fundam. Inform. 52(1-3): 15-38 (2002)
23EEMartin Kutrib, Jan-Thomas Löwe: Massively parallel fault tolerant computations on syntactical patterns. Future Generation Comp. Syst. 18(7): 905-919 (2002)
22 Martin Kutrib: Refining Nondeterminism Below Linear Time. Journal of Automata, Languages and Combinatorics 7(4): 533-547 (2002)
21 Andreas Klein, Martin Kutrib: Deterministic Turing machines in the range between real-time and linear-time. Theor. Comput. Sci. 289(1): 253-275 (2002)
2001
20EEMarkus Holzer, Martin Kutrib: Improving Raster Image Run-Length Encoding Using Data Order. CIAA 2001: 161-176
19EEMartin Kutrib: Efficient Universal Pushdown Cellular Automata and Their Application to Complexity. MCU 2001: 252-263
18EEAndreas Klein, Martin Kutrib: A Time Hierarchy for Bounded One-Way Cellular Automata. MFCS 2001: 439-450
2000
17 Martin Kutrib, Jan-Thomas Löwe: Fault Tolerant Parallel Pattern Recognition. ACRI 2000: 72-80
16EEThomas Buchholz, Andreas Klein, Martin Kutrib: Real-Time Language Recognition by Alternating Cellular Automata. IFIP TCS 2000: 213-225
15EEThomas Buchholz, Andreas Klein, Martin Kutrib: Iterative Arrays with Small Time Bounds. MFCS 2000: 243-252
14EEMartin Kutrib, Jan-Thomas Löwe: Massively Parallel Pattern Recognition with Link Failures. SOFSEM 2000: 392-401
13EEAndreas Klein, Martin Kutrib: Deterministic Turing Machines in the Range between Real-Time and Linear-Time Electronic Colloquium on Computational Complexity (ECCC) 7(75): (2000)
1999
12 Thomas Buchholz, Andreas Klein, Martin Kutrib: On tally languages and generalized interacting automata. Developments in Language Theory 1999: 316-325
11EEThomas Buchholz, Andreas Klein, Martin Kutrib: Iterative Arrays with a Wee Bit Alternation. FCT 1999: 173-184
10EEMartin Kutrib: Pushdown Cellular Automata. Theor. Comput. Sci. 215(1-2): 239-261 (1999)
1998
9EEThomas Buchholz, Andreas Klein, Martin Kutrib: One Guess One-Way Cellular Arrays. MFCS 1998: 807-815
8EEThomas Buchholz, Martin Kutrib: On Time Computability of Functions in One-Way Cellular Automata. Acta Inf. 35(4): 329-352 (1998)
1997
7 Thomas Buchholz, Martin Kutrib: On the power of one-way bounded cellular time computers. Developments in Language Theory 1997: 365-375
6 Martin Kutrib, Roland Vollmar, Thomas Worsch: Introduction to the Special Issue on Cellular Automata. Parallel Computing 23(11): 1567-1576 (1997)
5 Thomas Buchholz, Martin Kutrib: Some Relations Between Massively Parallel Arrays. Parallel Computing 23(11): 1643-1662 (1997)
1996
4 Alf-Christian Achilles, Martin Kutrib, Thomas Worsch: On Relations between Arrays of Processing Elements of Different Dimensionality. Parcella 1996: 13-20
1995
3 Martin Kutrib, Jörg Richstein: Real-Time One-Way Pushdown Cellular Automata Languages. Developments in Language Theory 1995: 420-429
1994
2 Martin Kutrib, Thomas Worsch: Investigation of Different Input Modes for Cellular Automata. Parcella 1994: 141-150
1991
1 Martin Kutrib, Roland Vollmar: Minimal Time Synchronization in Restricted Defective Cellular Automata. Elektronische Informationsverarbeitung und Kybernetik 27(3): 179-196 (1991)

Coauthor Index

1Alf-Christian Achilles [4]
2Suna Bensch [67]
3Henning Bordihn [36] [39] [40] [44] [45] [50] [56] [61] [67] [68] [73]
4Thomas Buchholz [5] [7] [8] [9] [11] [12] [15] [16] [24]
5Hermann Gruber [51] [59] [71]
6Markus Holzer [20] [26] [28] [30] [33] [35] [36] [37] [39] [40] [42] [44] [45] [46] [50] [51] [53] [56] [59] [61] [67] [69] [70] [71] [73] [74]
7Andreas Klein [9] [11] [12] [13] [15] [16] [18] [21] [24] [27] [29] [55] [57]
8Jan-Thomas Löwe [14] [17] [23] [25] [31]
9Andreas Malcher [38] [47] [48] [49] [52] [54] [58] [60] [62] [65] [66] [68] [69]
10Maurice Margenstern [32]
11Hartmut Messerschmidt [72]
12Friedrich Otto [72]
13Jens Reimann [53] [63] [64]
14Jörg Richstein [3]
15Hiroshi Umeo [32]
16Roland Vollmar [1] [6]
17Larissa Werlein [62]
18Thomas Worsch [2] [4] [6]
19Detlef Wotschke [38] [66]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)