Minimal Reversible Deterministic Finite Automata

M. Holzer, S. Jakobi, M. Kutrib
International Journal of Foundations of Computer Science, to appear


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


Revisiting the Cutting of the Firing Squad Synchronization

A. Dimitriadis, M. Kutrib, G.Ch. Sirakoulis
Natural Computing, to appear


Self-Verifying Pushdown Automata

H. Fernau, M. Kutrib, M. Wendlandt
In R. Freund, F. Mráz, D. Průša (eds.): Workshop on 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.): Workshop on 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


Descriptional Complexity of Limited Automata

M. Kutrib, G. Pighizzini, M. Wendlandt
Information and Computation, to appear


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


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


  18.10.2017
  Zurück zu M. Kutrib