Selected Publications by Martin Kutrib

On the Power of Pushing or Stationary Moves for Input-Driven Pushdown Automata

M. Kutrib, A. Malcher, M. Wendlandt
Theoretical Computer Science 996 (2024) Art. 114503

Reversible Computations of One-Way Counter Automata

M. Kutrib, A. Malcher
RAIRO - Theoretical Informatics and Applications 58 (2024) Art. 5

25 Editions of DCFS: Origins and Directions

J. Dassow, M. Kutrib, G. Pighizzini
EATCS Bulletin 141 (2023) pp. 34

Iterated Uniform Finite-State Transducers on Unary Languages

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
Theoretical Computer Science 969 (2023) Art. 114049

Sweeping Input-Driven Pushdown Automata

M. Kutrib
In B. Nagy (ed.): Implementation and Application of Automata (CIAA 2023), LNCS 14151, Springer 2023, 194-205

Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
Journal of Automata, Languages and Combinatorics 28 (2023) 59-88

Deterministic Real-Time Tree-Walking-Storage Automata

M. Kutrib, U. Meyer
In B. Nagy, R. Freund (eds.): Non-Classical Models of Automata and Applications (NCMA 2023), EPTCS 388, 2023, 48-62

Reversible Two-Party Computations

M. Kutrib, A. Malcher
In Z. Gazdag, S. Iván, G. Kovásznai (eds.): Automata and Formal Languages (AFL 2023), EPTCS 386, 2023, 142-154

Complexity of Exclusive Nondeterministic Finite Automata

M. Kutrib, A. Malcher, M. Wendlandt
In H. Bordihn, N. Tran, Gy. Vaszil (eds.): Descriptional Complexity of Formal Systems (DCFS 2023), LNCS 13918, Springer 2023, 121-133

Syntax Checking Either Way

M. Kutrib, U. Meyer
Theoretical Computer Science 966-967 (2023) Art. 114000

State Complexity of Finite Partial Languages

M. Kutrib, M. Wendlandt
Theoretical Computer Science 966-967 (2023) Art. 114001

Tree-Walking-Storage Automata

M. Kutrib, U. Meyer
In F. Drewes, M. Volkov (eds.): Developments in Language Theory (DLT 2023), LNCS 13911, Springer 2023, 182-194

Reversible Top-Down Syntax Analysis

M. Kutrib, U. Meyer
International Journal of Foundations of Computer Science 34 (2023) 225-251

Reversible Computations of One-Way Counter Automata

M. Kutrib, A. Malcher
In H. Bordihn, G. Horváth, G. Vaszil (eds.): Non-Classical Models of Automata and Applications (NCMA 2022), EPTCS 367, 2022, 126-142

State Complexity of Finite Partial Languages

M. Kutrib, M. Wendlandt
In Y.-S. Han, G. Vaszil (eds.): Descriptional Complexity of Formal Systems (DCFS 2022), LNCS 13439, Springer 2022, 170-183

One-Dimensional Pattern Generation by Cellular Automata

M. Kutrib, A. Malcher
Natural Computing 21 (2022) 361-375

Reversible Shrinking Two-Pushdown Automata

H.B. Axelsen, M. Kutrib, A. Malcher
Journal of Automata, Languages and Combinatorics 27 (2022) 47-77

Variants of String Assembling Systems

M. Kutrib, M. Wendlandt
Natural Computing, to appear

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
Fundamenta Informaticae 185 (2022) 337-356

Optimizing Reversible Programs

N. Deworetzki, M. Kutrib, U. Meyer, P. Ritzke
In C. A. Mezzina, K. Podlaski (eds.): Reversible Computation (RC 2022), LNCS 13354, Springer 2022, 224-238

On the Power of Pushing or Stationary Moves for Input-Driven Pushdown Automata

M. Kutrib, A. Malcher, M. Wendlandt
In P. Caron, L. Mignot (eds.): Implementation and Application of Automata (CIAA 2022), LNCS 13266, Springer 2022, 140-151

Input-Driven Double-Head Pushdown Automata

M. Holzer, M. Kutrib, A. Malcher, M. Wendlandt
International Journal of Foundations of Computer Science 33 (2022) 285-211

Iterative Arrays with Self-Verifying Communication Cell

M. Kutrib
Natural Computing 21 (2022) 39-51

Iterative Arrays with Finite Inter-Cell Communication

M. Kutrib, A. Malcher
Natural Computing 21 (2022) 3-15

Descriptional Complexity of Iterated Uniform Finite-State Transducers

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
Information and Computation 284 (2022) Art. 104691

Finite Automata with Undirected State Graphs

M. Kutrib, A. Malcher, C. Schneider
Acta Informatica 59 (2022) 163-181

Reversible Pushdown Transducers

B. Guillon, M. Kutrib, A. Malcher, L. Prigioniero
Information and Computation 281 (2021) Art. 104813

State Complexity of Partial Word Finite Automata

M. Kutrib, M. Wendlandt
In Y.-S. Han, S.-K. Ko (eds.): Descriptional Complexity of Formal Systems (DCFS 2021), LNCS 13037, Springer 2021, 113-124

String Assembling Systems: Comparison to Sticker Systems and Decidability

M. Kutrib, M. Wendlandt
In I. Kostitsyna, P. Orponen (eds.): Unconventional Computation and Natural Computation (UCNC 2021), LNCS 12984, Springer 2021, 101-115

Reversible Top-Down Syntax Analysis

M. Kutrib, U. Meyer
In N. Moreira, R. Reis (eds.): Developments in Language Theory (DLT 2021), LNCS 12811, Springer 2021, 255-266

Hot Current Topics of Descriptional Complexity

M. Kutrib, N. Moreira, G. Pighizzini, R. Reis
In M. Goedicke, E. Neuhold, K. Rannenberg (eds.): IFIP's Exciting First 60+ Years, IFIP Advances in Information and Communication Technology 600, Springer 2021, 3-28

Digging Input-Driven Pushdown Automata

M. Kutrib, A. Malcher
RAIRO - Theoretical Informatics and Applications 55 (2021) Art. 6

Boolean Kernels of Context-Free Languages

M. Kutrib, L. Prigioniero
In S. Maneth (ed.): Implementation and Application of Automata (CIAA 2021), LNCS 12803, Springer 2021, 152-164

Compiling Janus to RSSA

M. Kutrib, U. Meyer, N. Deworetzki, M. Schuster
In S. Yamashita, T. Yokoyama (eds.): Reversible Computation (RC 2021), LNCS 12805, Springer 2021, 64-78

String Generation by Cellular Automata

M. Kutrib, A. Malcher
Complex Systems 30 (2021) 111-132

Self-Verifying Pushdown and Queue Automata

H. Fernau, M. Kutrib, M. Wendlandt
Fundamenta Informaticae 180 (2021) 1-28

Two-Sided Strictly Locally Testable Languages

M. Holzer, M. Kutrib, F. Otto
Fundamenta Informaticae 180 (2021) 29-51

Input-Driven Multi-Counter Automata

M. Kutrib, A. Malcher, M. Wendlandt
Theoretical Computer Science 870 (2021) 121-136

Boosting Reversible Pushdown and Queue Machines by Preprocessing

H.B. Axelsen, M. Kutrib, A. Malcher, M. Wendlandt
International Journal of Foundations of Computer Science 31 (2020) 1021-1049

Iterated Uniform Finite-State Transducers on Unary Languages

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
In T. Bures, R. Dondi, J. Gamper, G. Guerrini T. Jurdzinski, C. Pahl, F. Sikora, P. W. H. Wong (eds.): Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), LNCS 12607, Springer 2021, 218-232

One-Dimensional Pattern Generation by Cellular Automata

M. Kutrib, A. Malcher
In T. M. Gwizdalla, L. Manzoni, G. Ch. Sirakoulis, S. Bandini, K. Podlaski (eds.): Cellular Automata for Research and Industry (ACRI 2020), LNCS 12599, Springer 2020, 46-55

On Two-Sided Locally Testable Languages

M. Kutrib, F. Otto
Journal of Automata, Languages and Combinatorics 25 (2020) 171-199

Automata that May Change Their Mind

M. Holzer, M. Kutrib
Journal of Automata, Languages and Combinatorics 25 (2020) 115-140

Self-Verifying Cellular Automata

M. Kutrib, Th. Worsch
Journal of Cellular Automata 15 (2020) 223-242

Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
In G. Jirásková, G. Pighizzini (eds.): Descriptional Complexity of Formal Systems (DCFS 2020), LNCS 12442, Springer 2020, 117-129

Cellular String Generators

M. Kutrib, A. Malcher
In H. Zenil (ed.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2020), LNCS 12286, Springer 2020, 59-70

Deterministic and Nondeterministic Iterated Uniform Finite-State Transducers: Computational and Descriptional Power

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
In M. Anselmo, G. Della Vedova, F. Manea, A. Pauly (eds.): Computability in Europe (CIE 2020), LNCS 12098, Springer 2020, 87-99

Kernels of Sub-Classes of Context-Free Languages

M. Kutrib
In A. Chatzigeorgiou, R. Dondi, H. Herodotou, Ch. A. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos, F. Sikora (eds.): Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), LNCS 12011, Springer 2020, 136-147

One-Time Nondeterministic Computations

M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 30 (2019) 1069-1089

Transducing Reversibly with Finite State Machines

M. Kutrib, A. Malcher, M. Wendlandt
Theoretical Computer Science 787 (2019) 111-126

Input-Driven Multi-Counter Automata

M. Kutrib, A. Malcher, M. Wendlandt
In M. Hospodár, G. Jirásková (eds.): Implementation and Application of Automata (CIAA 2019), LNCS 11601, Springer 2019, 197-208

Descriptional Complexity of Iterated Uniform Finite State Transducers

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
In M. Hospodár, G. Jirásková, S. Konstantinidis (eds.): Descriptional Complexity of Formal Systems (DCFS 2019), LNCS 11612, Springer 2019, 223-234

Non-Recursive Trade-Offs Are “Almost Everywhere”

M. Holzer, M. Kutrib
In F. Manea, B. Martin, D. Paulusma, G. Primiero (eds.): Computability in Europe (CIE 2019), LNCS 11558, Springer 2019, 25-36

Digging Input-Driven Pushdown Automata

M. Kutrib, A. Malcher
In R. Freund, M. Holzer, J.M. Sempere (eds.): Non-Classical Models of Automata and Applications (NCMA 2019), books@ocg.at, Volume 336, Austrian Computer Society 2019, 109-124

Iterative Arrays with Finite Inter-Cell Communication

M. Kutrib, A. Malcher
In A. Castillo-Ramirez, Pedro P.B. de Oliveira (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2019), LNCS 11525, Springer 2019, 35-47

Iterative Arrays with Self-Verifying Communication Cell

M. Kutrib, Th. Worsch
In A. Castillo-Ramirez, Pedro P.B. de Oliveira (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2019), LNCS 11525, Springer 2019, 77-90

Operational State Complexity and Decidability of Jumping Finite Automata

S. Beier, M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 30 (2019) 5-27

Diving Into the Queue

S. Beier, M. Kutrib, A. Malcher, M. Wendlandt
RAIRO - Theoretical Informatics and Applications 52 (2018) 89-110

Expressive Capacity of Subregular Expressions

M. Kutrib, M. Wendlandt
RAIRO - Theoretical Informatics and Applications 52 (2018) 201-218

Multi-Stranded String Assembling Systems

M. Kutrib, M. Wendlandt
In B. Catania, R. Královič, J.R. Nawrocki, G. Pighizzini (eds.): Current Trends in Theory and Practice of Computer Science (SOFSEM 2019), LNCS 11376, Springer 2019, 285-297

Self-Verifying Cellular Automata

M. Kutrib, Th. Worsch
In G. Mauri, S. El Yacoubi, A. Dennunzio, K. Nishinari, L. Manzoni (eds.): Cellular Automata for Research and Industry (ACRI 2018), LNCS 11115, Springer 2018, 340-351

Reversible Pushdown Transducers

B. Guillon, M. Kutrib, A. Malcher, L. Prigioniero
In M. Hoshi, S. Seki (eds.): Developments in Language Theory (DLT 2018), LNCS 11088, Springer 2018, 354-365

Revisiting the Cutting of the Firing Squad Synchronization

A. Dimitriadis, M. Kutrib, G.Ch. Sirakoulis
Natural Computing 17 (2018) 455-465

Automata that May Change Their Mind

M. Holzer, M. Kutrib
In R. Freund, M. Hospodár, G. Jirásková (eds.): Non-Classical Models of Automata and Applications (NCMA 2018), books@ocg.at, Volume 332, Austrian Computer Society 2018, 83-98

Two-Sided Locally Testable Languages

M. Kutrib, F. Otto
In R. Freund, M. Hospodár, G. Jirásková (eds.): Non-Classical Models of Automata and Applications (NCMA 2018), books@ocg.at, Volume 332, Austrian Computer Society 2018, 133-148

Boosting Pushdown and Queue Machines by Preprocessing

M. Kutrib, A. Malcher, M. Wendlandt
In C. Câmpeanu (ed.): Implementation and Application of Automata (CIAA 2018), LNCS 10977, Springer 2018, 28-40

Parametrizing String Assembling Systems

M. Kutrib, M. Wendlandt
In C. Câmpeanu (ed.): Implementation and Application of Automata (CIAA 2018), LNCS 10977, Springer 2018, 236-247

Finite Automata with Undirected State Graphs

M. Kutrib, A. Malcher, C. Schneider
In S. Konstantinidis, G. Pighizzini (eds.): Descriptional Complexity of Formal Systems (DCFS 2018), LNCS 10952, Springer 2018, 212-223

Queue Automata: Foundations and Developments

M. Kutrib, A. Malcher, M. Wendlandt
In A. Adamatzky (ed.): Reversibility and Universality. Emergence, Complexity and Computation, vol 30. Springer 2018, 385-431

Cellular Automata: Descriptional Complexity and Decidability

M. Kutrib, A. Malcher
In A. Adamatzky (ed.): Reversibility and Universality. Emergence, Complexity and Computation, vol 30. Springer 2018, 129-168

Descriptional Complexity of Limited Automata

M. Kutrib, G. Pighizzini, M. Wendlandt
Information and Computation 259 (2018) 259-276

Minimal Reversible Deterministic Finite Automata

M. Holzer, S. Jakobi, M. Kutrib
International Journal of Foundations of Computer Science 29 (2018) 251-270

Deterministic Stack Transducers

S. Bensch, J. Björklund, M. Kutrib
International Journal of Foundations of Computer Science 28 (2017) 583-601

The Degree of Irreversibility in Deterministic Finite Automata

H.B. Axelsen, M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 28 (2017) 503-522

Input-Driven Double-Head Pushdown Automata

M. Holzer, M. Kutrib, A. Malcher, M. Wendlandt
In E. Csuhaj-Varjú, P. Dömösi, G. Vaszil (eds.): Automata and Formal Languages (AFL 2017), EPTCS 252 (2017) 128-142

On the Descriptional Complexity of Operations on Semilinear Sets

S. Beier, M. Holzer, M. Kutrib
In E. Csuhaj-Varjú, P. Dömösi, G. Vaszil (eds.): Automata and Formal Languages (AFL 2017), EPTCS 252 (2017) 41-55

Shrinking One-Way Cellular Automata

M. Kutrib, A. Malcher, M. Wendlandt
Natural Computing 16 (2017) 383-396

Descriptional Complexity of Bounded Regular Languages

A. Herrmann, M. Kutrib, A. Malcher, M. Wendlandt
Journal of Automata, Languages and Combinatorics 22 (2017) 93-121

Tinput-Driven Pushdown, Counter, and Stack Automata

M. Kutrib, A. Malcher, M. Wendlandt
Fundamenta Informaticae 155 (2017) 59-88

Reversible Limited Automata

M. Kutrib, M. Wendlandt
Fundamenta Informaticae 155 (2017) 31-58

Self-Verifying Pushdown Automata

H. Fernau, M. Kutrib, M. Wendlandt
In R. Freund, F. Mráz, D. Průša (eds.): Non-Classical Models of Automata and Applications (NCMA 2017), books@ocg.at, Volume 329, Austrian Computer Society 2017, 103-117

Two-Sided Strictly Locally Testable Languages

F. Otto, M. Holzer, M. Kutrib
In R. Freund, F. Mráz, D. Průša (eds.): Non-Classical Models of Automata and Applications (NCMA 2017), books@ocg.at, Volume 329, Austrian Computer Society 2017, 135-150

Operational State Complexity and Decidability of Jumping Finite Automata

S. Beier, M. Holzer, M. Kutrib
In É. Charlier, J. Leroy, M. Rigo (eds.): Developments in Language Theory (DLT 2017), LNCS 10396, Springer 2017, 96-108

On Structure and Complexity of Some Subregular Language Families

M. Holzer, M. Kutrib
In S. Konstantinidis, N. Moreira, R. Reis, J. Shallit (eds.): The Role of Theory in Computer Science, Chapter 3, World Scientific 2017, 59-82

Reversible Nondeterministic Finite Automata

M. Holzer, M. Kutrib
In I. Phillips, H. Rahaman (eds.): Reversible Computation (RC 2017), LNCS 10301, Springer 2017, 35-51

Transducing Reversibly with Finite State Machines

M. Kutrib, A. Malcher, M. Wendlandt
In A. Carayol, C. Nicaud (eds.): Implementation and Application of Automata (CIAA 2017), LNCS 10329, Springer 2017, 151-162

One-Time Nondeterministic Computations

M. Holzer, M. Kutrib
In G. Pighizzini, C. Câmpeanu (eds.): Descriptional Complexity of Formal Systems (DCFS 2017), LNCS 10316, Springer 2017, 177-188

Fast One-Way Cellular Automata with Reversible Mealy Cells

M. Kutrib, A. Malcher, M. Wendlandt
In A. Dennunzio, E. Formenti, L. Manzoni, A. E. Porreca (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2017), LNCS 10248, Springer 2017, 139-150

The Chop of Languages

M. Holzer, S. Jakobi, M. Kutrib
Theoretical Computer Science 682 (2017) 122-137

One-Way Reversible Multi-Head Finite Automata

M. Kutrib, A. Malcher
Theoretical Computer Science 682 (2017) 149-164

Concatenation-Free Languages

M. Kutrib, M. Wendlandt
Theoretical Computer Science 679 (2017) 83-94

Reversible Queue Automata

M. Kutrib, A. Malcher, M. Wendlandt
Fundamenta Informaticae 148 (2016) 341-368

Iterative Arrays with Set Storage

M. Kutrib, A. Malcher
Journal of Cellular Automata 12 (2017) 7-26

When Input-Driven Pushdown Automata Meet Reversiblity

M. Kutrib, A. Malcher, M. Wendlandt
RAIRO - Theoretical Informatics and Applications 50 (2016) 313-330

Diving Into the Queue

S. Beier, M. Kutrib, A. Malcher, M. Wendlandt
In H. Bordihn, R. Freund, B. Nagy, G. Vaszil (eds.): Non-Classical Models of Automata and Applications (NCMA 2016), books@ocg.at, Volume 321, Austrian Computer Society 2016, 89-104

Expressive Capacity of Subregular Expressions

M. Kutrib, M. Wendlandt
In H. Bordihn, R. Freund, B. Nagy, G. Vaszil (eds.): Non-Classical Models of Automata and Applications (NCMA 2016), books@ocg.at, Volume 321, Austrian Computer Society 2016, 227-242

Cutting the Firing Squad Synchronization

A. Dimitriadis, M. Kutrib, G.Ch. Sirakoulis
In S. El Yacoubi, J. Wąs, S. Bandini (eds.): Cellular Automata for Research and Industry (ACRI 2016), LNCS 9863, Springer 2016, 123-133

Deterministic Stack Transducers

S. Bensch, J. Björklund, M. Kutrib
In Y. S. Han, K. Salomaa (eds.): Implementation and Application of Automata (CIAA 2016), LNCS 9705, Springer 2016, 27-38

The Degree of Irreversibility in Deterministic Finite Automata

H.B. Axelsen, M. Holzer, M. Kutrib
In Y. S. Han, K. Salomaa (eds.): Implementation and Application of Automata (CIAA 2016), LNCS 9705, Springer 2016, 15-26

Boosting Reversible Pushdown Machines by Preprocessing

H.B. Axelsen, M. Kutrib, A. Malcher, M. Wendlandt
In S. Devitt, I. Lanese (eds.): Reversible Computation (RC 2016), LNCS 9720, Springer 2016, 89-104

Descriptional Complexity of Bounded Regular Languages

A. Herrmann, M. Kutrib, A. Malcher, M. Wendlandt
In C. Câmpeanu, F. Manea, J. Shallit (eds.): Descriptional Complexity of Formal Systems (DCFS 2016), LNCS 9777, Springer 2016, 138-152

Reversible Shrinking Two-Pushdown Automata

H.B. Axelsen, M. Holzer, M. Kutrib, A. Malcher
In A. H. Dediu, J. Janousek, C. Martín-Vide, B. Truthe (eds.): Language and Automata Theory and Applications (LATA 2016), LNCS 9618, Springer 2016, 579-591

Input-Driven Queue Automata with Internal Transductions

M. Kutrib, A. Malcher, M. Wendlandt
In A. H. Dediu, J. Janousek, C. Martín-Vide, B. Truthe (eds.): Language and Automata Theory and Applications (LATA 2016), LNCS 9618, Springer 2016, 156-167

Set Automata

M. Kutrib, A. Malcher, M. Wendlandt
International Journal of Foundations of Computer Science 27 (2016) 187-214

Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities

H. Bordihn M. Kutrib, A. Malcher
International Journal of Foundations of Computer Science 26 (2015) 1101-1126

Tinput-Driven Pushdown Automata

M. Kutrib, A. Malcher, M. Wendlandt
In J. Durand-Lose, B. Nagy (eds.): Machines, Computations and Universality (MCU 2015), LNCS 9288, Springer 2015, 94-112

Reversible Limited Automata

M. Kutrib, M. Wendlandt
In J. Durand-Lose, B. Nagy (eds.): Machines, Computations and Universality (MCU 2015), LNCS 9288, Springer 2015, 113-128

When Input-Driven Pushdown Automata Meet Reversibility

M. Kutrib, A. Malcher, M. Wendlandt
In R. Freund, M. Holzer, N. Moreira, R. Reis (eds.): Non-Classical Models for Automata and Applications (NCMA 2015), books@ocg.at, Volume 318, Austrian Computer Society 2015, 141-157

Reversible and Irreversible Computations of Deterministic Finite-State Devices

M. Kutrib
In G. F. Italiano, G. Pighizzini, D. T. Sanella (ed.): Mathematical Foundations of Computer Science (MFCS 2015), LNCS 9234, Springer 2015, 38-52

Expressive Capacity of Concatenation Freeness

M. Kutrib, M. Wendlandt
In F. Drewes (ed.): Implementation and Application of Automata (CIAA 2015), LNCS 9223, Springer 2015, 199-210

Minimal Reversible Deterministic Finite Automata

M. Holzer, S. Jakobi, M. Kutrib
In I. Potapov (ed.): Developments in Language Theory (DLT 2015), LNCS 9168, Springer 2015, 276-287

A Hierarchy of Fast Reversible Turing Machines

H.B. Axelsen, S. Jakobi, M. Kutrib, A. Malcher
In J. Krivine, J.-B. Stefani (eds.): Reversible Computation (RC 2015), LNCS 9138, Springer 2015, 29-44

On Simulation Cost of Unary Limited Automata

M. Kutrib, M. Wendlandt
In J. Shallit, A. Okhotin (eds.): Descriptional Complexity of Formal Systems (DCFS 2015), LNCS 9118, Springer 2015, 153-164

Shrinking One-Way Cellular Automata

M. Kutrib, A. Malcher, M. Wendlandt
In J. Kari (ed.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2015), LNCS 9099, Springer 2015, 141-154

Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, M. Wendlandt
Theoretical Computer Science 578 (2015) 58-71

Deterministic One-Way Turing Machines with Sublinear Space Bounds

M. Kutrib, J. Provillard, G. Vaszil, M. Wendlandt
Fundamenta Informaticae 136 (2015) 139-155

Complexity of One-Way Cellular Automata

M. Kutrib
In T. Isokawa, K. Imai, N. Matsui, F. Peper, H. Umeo (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2014), LNCS 8996, Springer 2015, 3-18

Real-Time Reversible One-Way Cellular Automata

M. Kutrib, A. Malcher, M. Wendlandt
In T. Isokawa, K. Imai, N. Matsui, F. Peper, H. Umeo (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2014), LNCS 8996, Springer 2015, 56-69

Stateless One-Way Multi-Head Finite Automata with Pebbles

M. Kutrib, A. Malcher, M. Wendlandt
International Journal of Foundations of Computer Science 25 (2014) 1141-1159

Aspects of Reversibility for Classical Automata

M. Kutrib
In C. S. Calude, G. R. Freivalds, K. Iwama (eds.): Computing with New Resources, Essays Dedicated to Jozef Gruska on the Occasion of his 80th Birthday, LNCS 8808, Springer 2014, 83-98

Simulations of Unary One-Way Multi-Head Finite Automata

M. Kutrib, A. Malcher, M. Wendlandt
International Journal of Foundations of Computer Science 25 (2014) 877-896

Head and State Hierarchies for Unary Multi-Head Finite Automata

M. Kutrib, A. Malcher, M. Wendlandt
Acta Informatica 51 (2014) 553-569

Nonterminal Controlled String Assembling Systems

H. Bordihn, M. Kutrib, M. Wendlandt
Journal of Automata, Languages and Combinatorics 19 (2014) 33-44

Self-Assembling Pushdown Automata

M. Holzer, M. Kutrib
Journal of Automata, Languages and Combinatorics 19 (2014) 107-118

Iterative Arrays with Set Storage

M. Kutrib, A. Malcher
In J. Wąs, G. C. Sirakoulis, S. Bandini (eds.): Cellular Automata for Research and Industry (ACRI 2014), LNCS 8751, Springer 2014, 25-34

Measuring Communication in Automata Systems

M. Kutrib, A. Malcher
In A. M. Shur, M. V. Volkov (eds.): Developments in Language Theory (DLT 2014), LNCS 8633, Springer 2014, 260-274

Deterministic Set Automata

M. Kutrib, A. Malcher, M. Wendlandt
In A. M. Shur, M. V. Volkov (eds.): Developments in Language Theory (DLT 2014), LNCS 8633, Springer 2014, 303-314

Regularity and Size of Set Automata

M. Kutrib, A. Malcher, M. Wendlandt
In H. Jürgensen, J. Karhumäki, A. Okhotin (eds.): Descriptional Complexity of Formal Systems (DCFS 2014), LNCS 8614, Springer 2014, 281-293

Reversible Queue Automata

M. Kutrib, A. Malcher, M. Wendlandt
In S. Bensch, R. Freund, F. Otto (eds.): Non-Classical Models for Automata and Applications (NCMA 2014), books@ocg.at, Volume 304, Austrian Computer Society 2014, 163-178

Measuring Communication in Parallel Communicating Finite Automata

H. Bordihn M. Kutrib, A. Malcher
In Z. Ésik, Z. Fülöp (eds.): Automata and Formal Languages (AFL 2014), EPTCS 151 (2014) 124-138

nternational Conference Cellular Automata for Research and Industry (ACRI 2020) December 2--4, 2020, Łódź, Poland

Oblivious Two-Way Finite Automata: Decidability and Complexity

M. Kutrib, A. Malcher, G. Pighizzini
Information and Computation 237 (2014) 294-302

Degrees of Reversibility for DFA and DPDA

M. Kutrib, Th. Worsch
In Y. Shigeru, M. Shin-ichi (eds.): Reversible Computation (RC 2014), LNCS 8507, Springer 2014, 40-53

Bidirectional String Assembling Systems

M. Kutrib, M. Wendlandt
RAIRO - Theoretical Informatics and Applications 48 (2014) 39-59

Complexity of Operation Problems

M. Kutrib
In A. Beckmann, E. Csuhaj-Varjú, K. Meer (eds.): Computability in Europe (CIE 2014), LNCS 8493, Springer 2014, 255-264

Omega-rational languages: high complexity classes vs. Borel Hierarchy

E. Formenti, M. Holzer, M. Kutrib, J. Provillard
In A. H. Dediu, C. Martín-Vide, J. L. Sierra-Rodríguez, B. Truthe (eds.): Language and Automata Theory and Applications (LATA 2014), LNCS 8370, Springer 2014, 372-383

Parameterized Prefix Distance between Regular Languages

M. Kutrib, K. Meckel, M. Wendlandt
In V. Geffert, B. Preneel, B. Rovan, J. Stuller, A. M. Tjoa (eds.): Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), LNCS 8327, Springer 2014, 419-430

On the Descriptional Complexity of the Window Size for Deleting Restarting Automata

M. Kutrib, F. Otto
International Journal of Foundations of Computer Science 24 (2013) 831-846

Recent Trends in Descriptional Complexity of Formal Languages

M. Kutrib, G. Pighizzini
EATCS Bulletin 111 (2013) 70-86

One-Dimensional Cellular Automata Transducers

M. Kutrib, A. Malcher
Fundamenta Informaticae 126 (2013) 201-224

Deterministic One-Way Turing Machines with Sublinear Space Bounds

M. Kutrib, J. Provillard, G. Vaszil, M. Wendlandt
In S. Bensch, F. Drewes, R. Freund, F. Otto (eds.): Non-Classical Models for Automata and Applications (NCMA 2013), books@ocg.at, Volume 294, Austrian Computer Society 2013, 195-208

Size of Unary One-Way Multi-Head Finite Automata

M. Kutrib, A. Malcher, M. Wendlandt
In H. Jürgensen, R. Reis (eds.): Descriptional Complexity of Formal Systems (DCFS 2013), LNCS 8031, Springer 2013, 148-159

Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, M. Wendlandt
In S. Konstantinidis (ed.): Implementation and Application of Automata (CIAA 2013), LNCS 7982, Springer 2013, 232-243

Time-Symmetric Machines

M. Kutrib, Th. Worsch
In G.-W. Dueck, D. M. Miller (eds.): Reversible Computation (RC 2013), LNCS 7948, Springer 2013, 168-181

One-Way Multi-Head Finite Automata with Pebbles But No States

M. Kutrib, A. Malcher, M. Wendlandt
In M.-P. Béal, O. Carton (eds.): Developments in Language Theory (DLT 2013), LNCS 7907, Springer 2013, 313-324

The Size Impact of Little Iterative Array Resources

M. Kutrib, A. Malcher
Journal of Cellular Automata 7 (2012) 489-507

One-Way Reversible Multi-Head Finite Automata

M. Kutrib, A. Malcher
In R. Glück and T. Yokoyama (eds.): Reversible Computation (RC 2012), LNCS 7581, Springer 2013, 14-28

String Assembling Systems

M. Kutrib, M. Wendlandt
RAIRO - Theoretical Informatics and Applications 46 (2012) 593-613

Input-Driven Stack Automata

S. Bensch, M. Holzer, M. Kutrib, A. Malcher
In J. C. M. Baeten, T. Ball, F. S. de Boer (eds.): Theoretical Computer Science (IFIP TCS2012), LNCS 7604, Springer 2012, 28-42

Iterative Arrays: Little Resources Big Size Impact

M. Kutrib, A. Malcher
In G. C. Sirakoulis, S. Bandini (eds.): Cellular Automata for Research and Industry (ACRI 2012), LNCS 7495, Springer 2012, 42-51

Transductions Computed by One-Dimensional Cellular Automata

M. Kutrib, A. Malcher
In E. Formenti (ed.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2012), EPTCS 90 (2012) 194-207

Bidirectional String assembling Systems

M. Kutrib, M. Wendlandt
In R. Freund, M. Holzer, B. Truthe, U. Ultes-Nitsche (eds.): Non-Classical Models for Automata and Applications (NCMA 2012), books@ocg.at, Volume 290, Austrian Computer Society 2012, 107-121

Reversible Pushdown Automata

M. Kutrib, A. Malcher
Journal of Computer and System Sciences 78 (2012) 1814-1827

Nondeterministic State Complexity of Star-Free Languages

M. Holzer, M. Kutrib, K. Meckel
Theoretical Computer Science 450 (2012) 68-80

States and Heads Do Count For Unary Multi-Head Finite Automata

M. Kutrib, A. Malcher, M. Wendlandt
In H. C. Yen, O. H. Ibarra (eds.): Developments in Language Theory (DLT 2012), LNCS 7410, Springer 2012, 214-225

On CD-Systems of Stateless Deterministic Two-Phase RR(1)-Automata

M. Kutrib, F. Otto
In Languages Alive. Essays Dedicated to Jürgen Dassow on the Occasion of his 65th Birthday, LNCS 7300, Springer 2012, 111-137

Nondeterministic Cellular Automata and Languages

M. Kutrib
International Journal of General Systems 41 (2012) 555-568

On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata

M. Kutrib, F. Otto
In N. Moreira, R. Reis (eds.): Implementation and Application of Automata (CIAA 2012), LNCS 7381, Springer 2012, 253-264

On the Computational Capacity of Parallel Communicating Finite Automata

H. Bordihn, M. Kutrib, A. Malcher
International Journal of Foundations of Computer Science 23 (2012) 713-732

Oblivious Two-Way Finite Automata: Decidability and Complexity

M. Kutrib, A. Malcher, G. Pighizzini
In D. Fernández-Baca (ed.): Latin American Theoretical Informatics Symposium (LATIN 2012), LNCS 7256, Springer 2012, 518-529

The Magic Number Problem for Subregular Language Families

M. Holzer, S. Jakobi, M. Kutrib
International Journal of Foundations of Computer Science 23 (2012) 115-131

Hairpin Finite Automata

H. Bordihn, M. Holzer, M. Kutrib
Journal of Automata, Languages and Combinatorics 16 (2011) 91-107

Undecidability and Hierarchy Results for Parallel Communicating Finite Automata

H. Bordihn, M. Kutrib, A. Malcher
International Journal of Foundations of Computer Science 22 (2011) 1577-1592

The Complexity of Regular (Like) Expressions

M. Holzer, M. Kutrib
International Journal of Foundations of Computer Science 22 (2011) 1533-1548

Computational Complexity of Nurikabe

M. Holzer, A. Klein, M. Kutrib, O. Ruepp
Fundamenta Informaticae 110 (2011) 159-174

The Chop of Languages

M. Holzer, S. Jakobi, M. Kutrib
In Pál Dömösi, Szabolcs Iván (eds.): Automata and Formal Languages (AFL 2011), Institute of Mathematics and Informatics, College of Nyíregyháza, Hungary, 2011, 197-210

Nodes Connected by Path Languages

M. Holzer, M. Kutrib, U. Leiter
In G. Mauri, A. Leporati (eds.): Developments in Language Theory (DLT 2011), LNCS 6795, Springer 2011, 276-287

String Assembling Systems

M. Kutrib, M. Wendlandt
In R. Freund, M. Holzer, C. Mereghetti, F. Otto, B. Palano (eds.): Non-Classical Models of Automata and Applications (NCMA 2011), books@ocg.at, Volume 282, Austrian Computer Society 2011, 179-192

Nondeterministic State Complexity of Star-Free Languages

M. Holzer, M. Kutrib, K. Meckel
In B. Bouchou-Markhoff, P. Caron, J.-M. Champarnaud, D. Maurel (eds.): Implementation and Application of Automata (CIAA 2011), LNCS 6807, Springer 2011, 178-189

Gaining Power by Input Operations: Finite Automata and Beyond

M. Holzer, M. Kutrib
In B. Bouchou-Markhoff, P. Caron, J.-M. Champarnaud, D. Maurel (eds.): Implementation and Application of Automata (CIAA 2011), LNCS 6807, Springer 2011, 16-29

Nature-Based Problems in Cellular Automata

M. Kutrib
In B. Löwe, D. Normann, I. Soskov, A. Soskova (eds.): Models of Computation in Context (CIE 2011), LNCS 6735, Springer 2011, 171-180

Cellular Automata with Limited Inter-Cell Bandwidth

M. Kutrib, A. Malcher
Theoretical Computer Science 412 (2011) 3917-3931

Descriptional and Computational Complexity of Finite Automata - A Survey

M. Holzer, M. Kutrib
Information and Computation 209 (2011) 456-470

Undecidability of Operation Problems for T0L Languages and Subclasses

H. Bordihn, M. Holzer, M. Kutrib
Information and Computation 209 (2011) 344-352

Measuring Communication in Cellular Automata

M. Kutrib, A. Malcher
In J. Kari (ed.): Symposium on Cellular Automata - Journées Automates Cellulaires (JAC 2010), TUCS Lecture Notes 13, Turku Centre for Computer Science 2010, 13-30

Transductions Computed by Iterative Arrays

M. Kutrib, A. Malcher
In J. Kari (ed.): Symposium on Cellular Automata - Journées Automates Cellulaires (JAC 2010), TUCS Lecture Notes 13, Turku Centre for Computer Science 2010, 156-167

Multi-Head Finite Automata: Origins and Directions

M. Holzer, M. Kutrib, A. Malcher
Theoretical Computer Science 412 (2011) 83-96

On Stateless Deterministic Restarting Automata

M. Kutrib, H. Messerschmidt, F. Otto
Acta Informatica 47 (2010) 391-412

Two-Party Watson-Crick Computations

M. Kutrib, A. Malcher
In M. Domaratzki, K. Salomaa (eds.): Implementation and Application of Automata (CIAA 2010), LNCS 6482, Springer 2010, 191-200

Cellular Automata and the Quest for Nontrivial Artificial Self-reproduction

M. Holzer, M. Kutrib
In M. Gheorghe, T. Hinze, G. Păun (eds.): Conference on Membrane Computing (CMC 11), LNCS 6501, Springer 2010, 19-36

On Stateless Two-Pushdown Automata and Restarting Automata

M. Kutrib, H. Messerschmidt, F. Otto
International Journal of Foundations of Computer Science 21 (2010) 781-798

Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata

M. Holzer, M. Kutrib
In A. Kucera, I. Potapov (eds.): Reachability Problems (RP 2010), LNCS 6227, Springer 2010, 1-23

Undecidability and Hierarchy Results for Parallel Communicating Finite Automata

H. Bordihn, M. Kutrib, A. Malcher
In Y. Gao, H. Lu, S. Seki, S. Yu (eds.): Developments in Language Theory (DLT 2010), LNCS 6224, Springer 2010, 88-99

The Complexity of Regular (Like) Expressions

M. Holzer, M. Kutrib
In Y. Gao, H. Lu, S. Seki, S. Yu (eds.): Developments in Language Theory (DLT 2010), LNCS 6224, Springer 2010, 16-30

Cellular Automata With Sparse Communication

M. Kutrib, A. Malcher
Theoretical Computer Science 411 (2010) 3516-3526

The Magic Number Problem for Subregular Language Families

M. Holzer, S. Jakobi, M. Kutrib
In I. McQuillan, G. Pighizzini, B. Trost (eds.): Descriptional Complexity of Formal Systems (DCFS 2010), University of Saskatchewan, Saskatoon, Canada 2010, 135-146

The Size of One-Way Cellular Automata

M. Kutrib, J. Lefèvre, A. Malcher
In N. Fatès, J. Kari, T. Worsch (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2010), Discrete Mathematics and Theoretical Computer Science, Proc. AL (2010) 75-94

Reversible Pushdown Automata

M. Kutrib, A. Malcher
In A.-H. Dediu, H. Fernau, C. Martín-Vide (eds.): Language and Automata Theory and Applications (LATA 2010), LNCS 6031, Springer 2010, 368-379

On Measuring Non-Recursive Trade-Off

H. Gruber, M. Holzer, M. Kutrib
Journal of Automata, Languages and Combinatorics 15 (2010) 107-120

One-Way Cellular Automata, Bounded Languages, and Minimal Communication

M. Kutrib, A. Malcher
Journal of Automata, Languages and Combinatorics 15 (2010) 135-153

Descriptional Complexity - An Introductory Survey

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

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

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 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

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

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, G. Păun (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

	20.3.2024
	Zurück zu M. Kutrib