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