Selected Publications

On Stateless Deterministic Restarting Automata

M. Kutrib, H. Messerschmidt, F. Otto
Accepted at: International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2009), Špindlerův Mýn, Czech Republic, January 24-30, 2009

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

H. Gruber, M. Holzer, M. Kutrib
Fundamenta Informaticae, to appear

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

Cellular Automata and Language Theory

M. Kutrib
In R. Meyers (ed.): Encyclopedia of Complexity and System Science, Springer, to appear

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

State Complexity of NFA to DFA Conversion for Subregular Language Families

H. Bordihn, M. Holzer, M. Kutrib
In C. Câmpeanu, G. Pighizzini (eds.): Descriptional Complexity of Formal Systems (DCFS 2008), University of Prince Edward Island, Canada 2008, 85-96

On Stateless Two-Pushdown Automata and Restarting Automata

M. Kutrib, H. Messerschmidt, F. Otto
In E. Csuhaj-Varjú, Z. Ésik (eds.): Automata and Formal Languages (AFL 2008), Computer and Automation Research Institute, Hungarian Academy of Sciences, 2008, 257-268

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

Regulated Nondeterminism in Pushdown Automata

M. Kutrib, A. Malcher, L. Werlein
In J. Holub, J. Žďárek (eds.): Implementation and Application of Automata (CIAA 2007), LNCS 4783, Springer 2007, 85-96

Real-Time Reversible Iterative Arrays

M. Kutrib, A. Malcher
In E. Csuhaj-Varjú, Z. Ésik (eds.): Fundamentals of Computation Theory (FCT 2007), LNCS 4639, Springer 2007, 376-387

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


  14.10.2008
  Zurück zu M. Kutrib