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

Deterministic Real-Time Tree-Walking-Storage Automata

Reversible Two-Party Computations

Complexity of Exclusive Nondeterministic Finite Automata

Syntax Checking Either Way

State Complexity of Finite Partial Languages

Tree-Walking-Storage Automata

Reversible Top-Down Syntax Analysis

Reversible Computations of One-Way Counter Automata

State Complexity of Finite Partial Languages

One-Dimensional Pattern Generation by Cellular Automata

Reversible Shrinking Two-Pushdown Automata

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

Optimizing Reversible Programs

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

Input-Driven Double-Head Pushdown Automata

Iterative Arrays with Self-Verifying Communication Cell

Iterative Arrays with Finite Inter-Cell Communication

Descriptional Complexity of Iterated Uniform Finite-State Transducers

Finite Automata with Undirected State Graphs

Reversible Pushdown Transducers

State Complexity of Partial Word Finite Automata

String Assembling Systems: Comparison to Sticker Systems and Decidability

Reversible Top-Down Syntax Analysis

Hot Current Topics of Descriptional Complexity

Digging Input-Driven Pushdown Automata

Boolean Kernels of Context-Free Languages

Compiling Janus to RSSA

String Generation by Cellular Automata

Self-Verifying Pushdown and Queue Automata

Two-Sided Strictly Locally Testable Languages

Input-Driven Multi-Counter Automata

Boosting Reversible Pushdown and Queue Machines by Preprocessing

Iterated Uniform Finite-State Transducers on Unary Languages

One-Dimensional Pattern Generation by Cellular Automata

On Two-Sided Locally Testable Languages

Automata that May Change Their Mind

Self-Verifying Cellular Automata

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

Cellular String Generators

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

Kernels of Sub-Classes of Context-Free Languages

One-Time Nondeterministic Computations

Transducing Reversibly with Finite State Machines

Input-Driven Multi-Counter Automata

Descriptional Complexity of Iterated Uniform Finite State Transducers

Non-Recursive Trade-Offs Are “Almost Everywhere”

Digging Input-Driven Pushdown Automata

Iterative Arrays with Finite Inter-Cell Communication

Iterative Arrays with Self-Verifying Communication Cell

Operational State Complexity and Decidability of Jumping Finite Automata

Diving Into the Queue

Expressive Capacity of Subregular Expressions

Multi-Stranded String Assembling Systems

Self-Verifying Cellular Automata

Reversible Pushdown Transducers

Revisiting the Cutting of the Firing Squad Synchronization

Automata that May Change Their Mind

Two-Sided Locally Testable Languages

Boosting Pushdown and Queue Machines by Preprocessing

Parametrizing String Assembling Systems

Finite Automata with Undirected State Graphs

Queue Automata: Foundations and Developments

Cellular Automata: Descriptional Complexity and Decidability

Descriptional Complexity of Limited Automata

Minimal Reversible Deterministic Finite Automata

Deterministic Stack Transducers

The Degree of Irreversibility in Deterministic Finite Automata

Input-Driven Double-Head Pushdown Automata

On the Descriptional Complexity of Operations on Semilinear Sets

Shrinking One-Way Cellular Automata

Descriptional Complexity of Bounded Regular Languages

Tinput-Driven Pushdown, Counter, and Stack Automata

Reversible Limited Automata

Self-Verifying Pushdown Automata

Two-Sided Strictly Locally Testable Languages

Operational State Complexity and Decidability of Jumping Finite Automata

On Structure and Complexity of Some Subregular Language Families

Reversible Nondeterministic Finite Automata

Transducing Reversibly with Finite State Machines

One-Time Nondeterministic Computations

Fast One-Way Cellular Automata with Reversible Mealy Cells

The Chop of Languages

One-Way Reversible Multi-Head Finite Automata

Concatenation-Free Languages

Reversible Queue Automata

Iterative Arrays with Set Storage

When Input-Driven Pushdown Automata Meet Reversiblity

Diving Into the Queue

Expressive Capacity of Subregular Expressions

Cutting the Firing Squad Synchronization

Deterministic Stack Transducers

The Degree of Irreversibility in Deterministic Finite Automata

Boosting Reversible Pushdown Machines by Preprocessing

Descriptional Complexity of Bounded Regular Languages

Reversible Shrinking Two-Pushdown Automata

Input-Driven Queue Automata with Internal Transductions

Set Automata

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

Tinput-Driven Pushdown Automata

Reversible Limited Automata

When Input-Driven Pushdown Automata Meet Reversibility

Reversible and Irreversible Computations of Deterministic Finite-State Devices

Expressive Capacity of Concatenation Freeness

Minimal Reversible Deterministic Finite Automata

A Hierarchy of Fast Reversible Turing Machines

On Simulation Cost of Unary Limited Automata

Shrinking One-Way Cellular Automata

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

Deterministic One-Way Turing Machines with Sublinear Space Bounds

Complexity of One-Way Cellular Automata

Real-Time Reversible One-Way Cellular Automata

Stateless One-Way Multi-Head Finite Automata with Pebbles

Aspects of Reversibility for Classical Automata

Simulations of Unary One-Way Multi-Head Finite Automata

Head and State Hierarchies for Unary Multi-Head Finite Automata

Nonterminal Controlled String Assembling Systems

Self-Assembling Pushdown Automata

Iterative Arrays with Set Storage

Measuring Communication in Automata Systems

Deterministic Set Automata

Regularity and Size of Set Automata

Reversible Queue Automata

Measuring Communication in Parallel Communicating Finite Automata

Degrees of Reversibility for DFA and DPDA

Bidirectional String Assembling Systems

Complexity of Operation Problems

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

Parameterized Prefix Distance between Regular Languages

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

Recent Trends in Descriptional Complexity of Formal Languages

One-Dimensional Cellular Automata Transducers

Deterministic One-Way Turing Machines with Sublinear Space Bounds

Size of Unary One-Way Multi-Head Finite Automata

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

Time-Symmetric Machines

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

The Size Impact of Little Iterative Array Resources

One-Way Reversible Multi-Head Finite Automata

String Assembling Systems

Input-Driven Stack Automata

Iterative Arrays: Little Resources Big Size Impact

Transductions Computed by One-Dimensional Cellular Automata

Bidirectional String assembling Systems

Reversible Pushdown Automata

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

	09.04.2025
	Zurück zu M. Kutrib