Selected Publications


Descriptional Complexity - An Introductory Survey

M. Holzer, M. Kutrib
In C. Martín-Vide (ed.): Scientific Applications of Language Methods, Imperial College Press 2010, to appear


Reversible Pushdown Automata

M. Kutrib, A. Malcher
Accepted at: International Conference on Language and Automata Theory and Applications (LATA 2010), May 24-28, 2010, Trier, Germany


Real-Time Reversible Iterative Arrays

M. Kutrib, A. Malcher
Theoretical Computer Science 411 (2010) 812-822


On Input-Revolving Deterministic and Nondeterministic Finite Automata

S. Bensch, H. Bordihn, M. Holzer, M. Kutrib
Information and Computation 207 (2009) 1140--1155


On One-Way One-Bit O(One)-Message Cellular Automata

M. Kutrib, A. Malcher
Electronic Notes in Theoretical Computer Science 252 (2009) 77-91


On Stateless Two-Pushdown Automata and Restarting Automata

M. Kutrib, H. Messerschmidt, F. Otto
International Journal of Foundations of Computer Science, to appear


Nondeterministic Finite Automata - Recent Results on the Descriptional and Computational Complexity

M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 20 (2009) 563-580


Cellular Automata and Language Theory

M. Kutrib
In R. Meyers (ed.): Encyclopedia of Complexity and System Science, Springer 2009, 800-823


Regulated Nondeterminism in Pushdown Automata

M. Kutrib, A. Malcher, L. Werlein
Theoretical Computer Science 410 (2009) 3447-3460


Self-Assembling Finite Automata

A. Klein, M. Kutrib
Journal of Automata, Languages and Combinatorics 14 (2009) 75-92


Determinization of Finite Automata Accepting Subregular Languages

H. Bordihn, M. Holzer, M. Kutrib
Theoretical Computer Science 410 (2009), 3209-3222


Computations and Decidability of Iterative Arrays with Restricted Communication

M. Kutrib, A. Malcher
Parallel Processing Letters 19 (2009) 247-264


On Measuring Non-Recursive Trade-Offs

H. Gruber, M. Holzer, M. Kutrib
In J. Dassow, G. Pighizzini, B. Truthe (eds.): Descriptional Complexity of Formal Systems (DCFS 2009), Otto-von-Guericke-Universität Magdeburg, Germany 2009, 187-198


On the Number of Membranes in Unary P Systems

R. Freund, A. Klein, M. Kutrib
In J. Dassow, G. Pighizzini, B. Truthe (eds.): Descriptional Complexity of Formal Systems (DCFS 2009), Otto-von-Guericke-Universität Magdeburg, Germany 2009, 139-149


Bounded Languages Meet Cellular Automata with Sparse Communication

M. Kutrib, A. Malcher
In J. Dassow, G. Pighizzini, B. Truthe (eds.): Descriptional Complexity of Formal Systems (DCFS 2009), Otto-von-Guericke-Universität Magdeburg, Germany 2009, 211-222


Cellular Automata With Sparse Communication

M. Kutrib, A. Malcher
In S. Maneth (ed.): Implementation and Application of Automata (CIAA 2009), LNCS 5642, Springer 2009, 34-43


More on the Size of Higman-Haines Sets: Effective Constructions

H. Gruber, M. Holzer, M. Kutrib
Fundamenta Informaticae 91 (2009) 105-121


Descriptional and Computational Complexity of Finite Automata

M. Holzer, M. Kutrib
In A. H. Dediu, A. M. Ionescu, C. Martín-Vide (eds.): Language and Automata Theory and Applications (LATA 2009), LNCS 5457, Springer 2009, 23-42


Undecidability of Operation Problems for T0L Languages and Subclasses

H. Bordihn, M. Holzer, M. Kutrib
In A. H. Dediu, A. M. Ionescu, C. Martín-Vide (eds.): Language and Automata Theory and Applications (LATA 2009), LNCS 5457, Springer 2009, 236-246


On Stateless Deterministic Restarting Automata

M. Kutrib, H. Messerschmidt, F. Otto
In M. Nielsen, A. Kucera, P. B. Miltersen, C. Palamidessi, P. Tuma, F. D. Valencia (eds.): Theory and Practice of Computer Science (SOFSEM 2009), LNCS 5404, Springer 2009, 353-364


Multi-Head Finite Automata: Characterizations, Concepts and Open Problems

M. Holzer, M. Kutrib, A. Malcher
In T. Neary, D. Woods, A. K. Seda, N. Murphy (eds.): The Complexity of Simple Programs (CSP 2008), Cork University Press, Ireland 2008, 117-136


Succinct Description of Regular Languages by Weak Restarting Automata

M. Kutrib, J. Reimann
Information and Computation 206 (2008) 1152-1160

Fast Reversible Language Recognition Using Cellular Automata

M. Kutrib, A. Malcher
Information and Computation 206 (2008) 1142-1151


Optimal Simulations of Weak Restarting Automata

M. Kutrib, J. Reimann
International Journal of Foundations of Computer Science 19 (2008), 795-811


On the Computational Capacity of Parallel Communicating Finite Automata

H. Bordihn, M. Kutrib, A. Malcher
In M. Ito, M. Toyama (eds.): Developments in Language Theory (DLT 2008), LNCS 5257, Springer 2008, 146-157


Deterministic Input-Reversal and Input-Revolving Finite Automata

S. Bensch, H. Bordihn, M. Holzer, M. Kutrib
In C. Martín-Vide, F. Otto, H. Fernau (eds.): Language and Automata Theory and Applications (LATA 2008), LNCS 5196, Springer 2008, 113-124


Nondeterministic Finite Automata - Recent Results on the Descriptional and Computational Complexity

M. Holzer, M. Kutrib
In O. H. Ibarra, B. Ravikumar (eds.): Implementation and Application of Automata (CIAA 2008), LNCS 5148, Springer 2008, 1-16


The Boolean Closure of Linear Context-Free Languages

M. Kutrib, A. Malcher, D. Wotschke
Acta Informatica 45 (2008) 177-191


Cellular Automata - A Computational Point of View

M. Kutrib
In G. Bel-Enguix, M. D. Jiménez-López, C. Martín-Vide (eds.): New Developments in Formal Languages and Applications, Chapter 6, Springer 2008, 183-227


Efficient Pushdown Cellular Automata: Universality, Time and Space Hierarchies

M. Kutrib
Journal of Cellular Automata 3 (2008), 93-114


When Church-Rosser Becomes Context Free

M. Kutrib, A. Malcher
International Journal of Foundations of Computer Science 18 (2007), 1293-1302


The Size of Higman-Haines Sets

H. Gruber, M. Holzer, M. Kutrib
Theoretical Computer Science 387 (2007), 167-176


Context-Free Grammars with Linked Nonterminals

A. Klein, M. Kutrib
International Journal of Foundations of Computer Science 18 (2007), 1271-1282


Non-Recursive Trade-Offs for Deterministic Restarting Automata

M. Holzer, M. Kutrib, J. Reimann
Journal of Automata, Languages and Combinatorics 12 (2007), 195-213


Finite Turns and the Regular Closure of Linear Context-Free Languages

M. Kutrib, A. Malcher
Discrete Applied Mathematics 155 (2007), 2152-2164


Hybrid Extended Finite Automata

H. Bordihn, M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 18 (2007), 745-760


Hairpin Finite Automata

H. Bordihn, M. Holzer, M. Kutrib
In T. Harju, J. Karhumäki, A. Lepistö (eds.): Developments in Language Theory (DLT 2007), LNCS 4588, Springer 2007, 108-119


Context-Dependent Nondeterminism for Pushdown Automata

M. Kutrib, A. Malcher
Theoretical Computer Science 376 (2007), 101-111


Cellular Devices and Unary Languages

A. Klein, M. Kutrib
Fundamenta Informaticae 78 (2007), 343-368


Variable Complexity of Simple Programs

M. Holzer, M. Kutrib
Fundamenta Informaticae 74 (2006), 511-528


Fast Iterative Arrays with Restricted Inter-Cell Communication: Constructions and Decidability

M. Kutrib, A. Malcher
In R. Kralovic, P. Urzyczyn (eds.): Mathematical Foundations of Computer Science 2006 (MFCS 2006), LNCS 4162, Springer 2006, 634-645


Fast Cellular Automata with Restricted Inter-Cell Communication: Computational Capacity

M. Kutrib, A. Malcher
In G. Navarro, L. Bertossi, Y. Kohayakawa (eds.): Theoretical Computer Science (IFIP TCS 2006), IFIP 209, Springer 2006, 151-164


The Phenomenon of Non-Recursive Trade-Offs

M. Kutrib
International Journal of Foundations of Computer Science 16 (2005), 957-973


Revolving-Input Finite Automata

H. Bordihn, M. Holzer, M. Kutrib
In C. De Felice, A. Restivo (eds.): Developments in Language Theory (DLT 2005), LNCS 3572, Springer 2005, 168-179

Unsolvability Levels of Operation Problems for Subclasses of Context-Free Languages

H. Bordihn, M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 16 (2005), 423-440


On the Descriptional Power of Heads, Counters, and Pebbles

M. Kutrib
Theoretical Computer Science 330 (2005), 311-324


On the Descriptional Complexity of Finite Automata With Modified Acceptance Conditions

M. Holzer, M. Kutrib
Theoretical Computer Science 330 (2005), 267-285


Economy of Description for Basic Constructions on Rational Transductions

H. Bordihn, M. Holzer, M. Kutrib
Journal of Automata, Languages and Combinatorics 9 (2004), 175-188


Register Complexity of LOOP-, WHILE-, and GOTO-Programs

M. Holzer, M. Kutrib
In M. Margenstern (ed.): Machines, Computations and Universality (MCU 2004), LNCS 3354, Springer 2005, 233-244


Input Reversals and Iterated Pushdown Automata -
A New Characterization of Khabbaz Geometric Hierarchy of Languages

H. Bordihn, M. Holzer, M. Kutrib
In C. S. Calude, E. Calude, M. J. Dinneen (eds.): Developments in Language Theory (DLT 2004), LNCS 3340, Springer 2004, 102-113


On the NP-Completeness of the NURIKABE Pencil Puzzle and Variants Thereof

M. Holzer, A. Klein, M. Kutrib
In P. Ferragina, R. Grossi (eds.): Fun with Algorithms 2004 (FUN 2004), Edizioni PLUS, Università di Pisa, 2004, 77-89


Nondeterministic Descriptional Complexity of Regular Languages

M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 14 (2003), 1087-1102


The Fault-Tolerant Early Bird Problem

B. Fay, M. Kutrib
IEICE Transactions on Information and Systems E87-D (2004), 687-693


Space- and Time-Bounded Nondeterminism for Cellular Automata

M. Kutrib, J.-T. Löwe
Fundamenta Informaticae 58 (2003), 273-293


Dimension- and Time-Hierarchies for Small Time Bounds

M. Kutrib
In A. Lingas, B. J. Nilsson (eds.): Fundamentals of Computation Theory (FCT 2003), LNCS 2751, Springer 2003, 321-332


Flip-Pushdown Automata: Nondeterminism is Better Than Determinism

M. Holzer, M. Kutrib
In Z. Ésik, Z. Fülöp (eds.): Developments in Language Theory (DLT 2003), LNCS 2710, Springer 2003, 361-372


Fast One-Way Cellular Automata

A. Klein, M. Kutrib
Theoretical Computer Science 295 (2003), 233-250


Flip-Pushdown Automata: k+1 Pushdown Reversals are Better Than k

M. Holzer, M. Kutrib
In J. C. M. Baeten, J. K. Lenstra, J. Parrow, G. J. Woeginger (eds.): Automata, Languages and Programming (ICALP 2003), LNCS 2719, Springer 2003, 490-501


Refining Nondeterminism Below Linear-Time

M. Kutrib
Journal of Automata, Languages and Combinatorics 7 (2002), 533-547


On Interacting Automata with Limited Nondeterminism

Th. Buchholz, A. Klein, M. Kutrib
Fundamenta Informaticae 52 (2002), 15-38


Deterministic Turing machines in the range between real-time and linear-time

A. Klein, M. Kutrib
Theoretical Computer Science 289 (2002), 253-275
Preprint: Electronic Colloquium on Computational Complexity, Research Report TR00-75, 2000


Unary Language Operations and Their Nondeterministic State Complexity

M. Holzer, M. Kutrib
In M. Ito, M. Toyama (eds.): Developments in Language Theory (DLT 2002), LNCS 2450, Springer 2003, 162-172


State Complexity of Basic Operations on Nondeterministic Finite Automata

M. Holzer, M. Kutrib
In J.-M. Champarnaud, D. Maurel (eds.): Implementation and Application of Automata (CIAA 2002), LNCS 2608, Springer 2003, 148-157


String Transformation for n-Dimensional Image Compression

M. Kutrib, J.-T. Löwe
In W. I. Grosky, F. Plásil (eds.): Sofsem 2002 - Theory and Practice of Informatics, LNCS 2540, Springer 2002, 208-217


Self-Assembling Finite Automata

A. Klein, M. Kutrib
In O. H. Ibarra, L. Zhang (eds.): Computing and Combinatorics (COCOON 2002), LNCS 2387, Springer 2002, 310-319


Improving Raster Image Run-Length Encoding Using Data Order

M. Holzer, M. Kutrib
In B. W. Watson, D. Wood (eds.): Implementation and Application of Automata (CIAA 2001), LNCS 2494, Springer 2002, 161-176

Massively Parallel Fault Tolerant Computations on Syntactical Patterns

M. Kutrib, J.-T. Löwe
Future Generation Computer Systems, Elsevier, 18 (2002) 905-919


A Time Hierarchy for Bounded One-Way Cellular Automata

A. Klein, M. Kutrib
In J. Sgall, A. Pultr, P. Kolman (eds.): Mathematical Foundations of Computer Science 2001 (MFCS 2001), LNCS 2136, Springer 2001, 439-450


Efficient universal pushdown cellular automata and their application to complexity

M. Kutrib
In M. Margenstern, Y. Rogozhin (eds.): Machines, Computations and Universality (MCU 2001), LNCS 2055, Springer 2001, 252-263


On tally languages and generalized interacting automata

Th. Buchholz, A. Klein, M. Kutrib
In G. Rozenberg, W. Thomas (eds.): Developments in Language Theory IV. Foundations, Applications, and Perspectives, World Scientific Publishing, Singapore 2000, 316-325


Automata Arrays and Context-Free Languages

M. Kutrib
In C. Martín-Vide, V. Mitrana (eds.): Where Mathematics, Computer Science, Linguistics and Biology Meet, Kluwer, Dordrecht 2001, 139-148


Massively parallel pattern recognition with link failures

M. Kutrib, J.-T. Löwe
In V. Hlavac, K. G. Jeffery, J. Wiedermann (eds.): Sofsem 2000 - Theory and Practice of Informatics, LNCS 1963, Springer 2000, 392-401


Fault tolerant parallel pattern recognition

M. Kutrib, J.-T. Löwe
In S. Bandini (eds.): Theoretical and Practical Issues on Cellular Automata (ACRI 2000), Springer 2000, 72-80


Iterative arrays with small time bounds

Th. Buchholz, A. Klein, M. Kutrib
In M. Nielsen, B. Rovan (eds.): Mathematical Foundations of Computer Science 2000 (MFCS 2000), LNCS 1893, Springer 2000, 243-252


Real-Time Language Recognition by Alternating Cellular Automata

Th. Buchholz, A. Klein, M. Kutrib
In J. van Leeuwen et al. (eds.): Theoretical Computer Science. Exploring New Frontiers of Theoretical Informatics (IFIP TCS2000), LNCS 1872, Springer 2000, 213-225


Iterative arrays with limited nondeterministic communication cell

Th. Buchholz, A. Klein, M. Kutrib
In M. Ito, T. Imaoka (eds.): Words, Languages & Combinatorics III, World Scientific Publishing, Singapore 2003, 73-87


Iterative arrays with a wee bit alternation

Th. Buchholz, A. Klein, M. Kutrib
In G. Ciobanu, Gh. Paun (eds.): Fundamentals of Computation Theory 1999 (FCT'99), LNCS 1684, Springer 1999, 173-184


On time reduction and simulation in cellular spaces

Th. Buchholz, A. Klein, M. Kutrib
International Journal of Computer Mathematics 71 (1999), 459-474


Pushdown cellular automata

M. Kutrib
Theoretical Computer Science 215 (1999), 239-261


One guess one-way cellular arrays

Th. Buchholz, A. Klein, M. Kutrib
In L. Brim, J. Gruska, J. Zlatuska (eds.): Mathematical Foundations of Computer Science 1998 (MFCS'98), LNCS 1450, Springer 1998, 807-815


On time computability of functions in one-way cellular automata

Th. Buchholz, M. Kutrib
Acta Informatica 35 (1998), 329-352


Some relations between massively parallel arrays

Th. Buchholz, M. Kutrib
Parallel Computing 23 (1997), 1643-1662


On the power of one-way bounded cellular time computers

Th. Buchholz, M. Kutrib
In S. Bozapalidis (ed.): Developments in Language Theory, Aristotle University of Thessaloniki, Greece 1997, 365-375


On relations between arrays of processing elements of different dimensionality

A.-C. Achilles, M. Kutrib, Th. Worsch
In R. Vollmar, W. Erhard, V. Jossifov (eds.): PARCELLA '96, Akademie Verlag, Berlin 1996, 13-20


Real-Time One-Way Pushdown Cellular Automata Languages

M. Kutrib, J. Richstein
In J. Dassow, G. Rozenberg, A. Salomaa (eds.): Developments in Language Theory II. At the Crossroads of Mathematics, Computer Science and Biology, World Scientific Publishing, Singapore 1996, 420-429


The firing squad synchronization problem in defective cellular automata

M. Kutrib, R. Vollmar
IEICE Transactions on Information and Systems E78-D (1995), 895-900


Investigation of different input modes for cellular automata

M. Kutrib, Th. Worsch
In Ch. Jesshope, V. Jossifov, W. Wilhelmi (eds.): PARCELLA '94, Akademie Verlag, Berlin 1994, 141-150


Minimal time synchronization in restricted defective cellular automata

M. Kutrib, R. Vollmar
Journal of Information Processing and Cybernetics EIK 27 (1991), 179-196


  8.2.2010
  Zurück zu M. Kutrib