Selected Publications


Peer-Reviewed Journal Papers

Reversible two-party computations

M. Kutrib, A. Malcher
International Journal of Foundations of Computer Science, accepted for publication

On the power of pushing or stationary moves for input-driven pushdown automata

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

Reversible computations of one-way counter automata

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

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

Iterated uniform finite-state transducers on unary languages

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

One-dimensional pattern generation by cellular automata

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

Reversible shrinking two-pushdown automata

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

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

Input-driven double-head pushdown automata

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

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) 104691 (17 p.)

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) 104813 (16 p.)

Digging input-driven pushdown automata

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

String generation by cellular automata

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

Input-driven multi-counter automata

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

Decidability questions for insertion systems and related models

A. Malcher
Fundamenta Informaticae, 180 (2021) 53-76

Boosting reversible pushdown and queue machines by preprocessing

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

Hierarchies and undecidability results for iterative arrays with sparse communication

A. Malcher
Natural Computing, 19 (2020), 797-809

Transducing reversibly with finite state machines

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

Diving into the queue

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

Descriptional complexity of bounded regular languages

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

Shrinking one-way cellular automata

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

Tinput-driven pushdown, counter, and stack automata

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

One-way reversible multi-head finite automata

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

Iterative arrays with set storage

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

When input-driven pushdown automata meet reversibility

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

Reversible queue automata

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

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, decidabilites, and undecidabilities

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

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

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

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

Oblivious two-way finite automata: decidability and complexity

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

One-dimensional cellular automaton transducers

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

Descriptional complexity of bounded context-free languages

A. Malcher, G. Pighizzini
Information and Computation, 227 (2013), 1-20

Descriptional complexity of pushdown store languages

A. Malcher, K. Meckel, C. Mereghetti, B. Palano
Journal of Automata, Languages and Combinatorics, 17 (2012), 225-244

The size impact of little iterative array resources

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

Reversible pushdown automata

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

Descriptional complexity of two-way pushdown automata with restricted head reversals

A. Malcher, C. Mereghetti, B. Palano
Theoretical Computer Science, 449 (2012), 119-133

First-order logics: some characterizations and closure properties

C. Choffrut, A. Malcher, C. Mereghetti, B. Palano
Acta Informatica, 49 (2012), 225-248

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

In memoriam Chandra Kintala

M. Kappes, A. Malcher, D. Wotschke
International Journal of Foundations of Computer Science, 23 (2012), 5-19

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

Cellular automata with limited inter-cell bandwidth

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

Multi-Head finite automata: origins and directions

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

One-way cellular automata, bounded languages, and minimal communication

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

Sublinearly space bounded iterative arrays

A. Malcher, C. Mereghetti, B. Palano
International Journal of Foundations of Computer Science, 21 (2010), 843-858

Cellular automata with sparse communication

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

Real-time reversible iterative arrays

M. Kutrib, A. Malcher
Theoretical Computer Science, 411 (2010), 812-822

Regulated nondeterminism in pushdown automata

M. Kutrib, A. Malcher, L. Werlein
Theoretical Computer Science, 410 (2009), 3447-3460

Computations and decidability of iterative arrays with restricted communication

M. Kutrib, A. Malcher
Parallel Processing Letters, 19 (2009), 247-264

Fast reversible language recognition using cellular automata

M. Kutrib, A. Malcher
Information and Computation, 206 (2008), 1142-1151

Descriptional complexity of splicing systems

R. Loos, A. Malcher, D. Wotschke
International Journal of Foundations of Computer Science 19 (2008), 813-826

The Boolean closure of linear context-free languages

M. Kutrib, A. Malcher, D. Wotschke
Acta Informatica 45 (2008), 177-191

On recursive and non-recursive trade-offs between finite-turn pushdown automata

A. Malcher
Journal of Automata, Languages and Combinatorics 12 (2007), 265-277

When Church-Rosser becomes context free

M. Kutrib, A. Malcher
International Journal of Foundations of Computer Science 18 (2007), 1293-1302

On metalinear parallel communicating grammar systems

A. Malcher, B. Sunckel
International Journal of Foundations of Computer Science 18 (2007), 1313-1322

Finite turns and the regular closure of linear context-free languages

M. Kutrib, A. Malcher
Discrete Applied Mathematics 155 (2007), 2152-2164

Context-dependent nondeterminism for pushdown automata

M. Kutrib, A. Malcher
Theoretical Computer Science 376 (2007), 101-111

On two-way communication in cellular automata with a fixed number of cells

A. Malcher
Theoretical Computer Science 330 (2005), 325-338

On the descriptional complexity of iterative arrays

A. Malcher
IEICE Transactions on Information and Systems E87-D (2004), 721-725

Minimizing finite automata is computationally hard

A. Malcher
Theoretical Computer Science 327 (2004), 375-390

On one-way cellular automata with a fixed number of cells

A. Malcher
Fundamenta Informaticae 58 (2003), 355-368

Descriptional complexity of machines with limited resources

J. Goldstine, M. Kappes, C. Kintala, H. Leung, A. Malcher, D. Wotschke
Journal of Universal Computer Science 8 (2002), 193-234

Descriptional complexity of cellular automata and decidability

A. Malcher
Journal of Automata, Languages and Combinatorics 7 (2002), 549-560



Peer-Reviewed Conference Papers

Complexity of unary exclusive nondeterministic finite automata

M. Kutrib, A. Malcher, M. Wendlandt
In F. Manea, G. Pighizzini (eds.): Non-Classical Models of Automata and Applications (NCMA 2024), EPTCS 407, 2024, 136-149

On properties of languages accepted by deterministic pushdown automata with translucent input letters

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, P. Raucci, M. Wendlandt
In S. Z. Fazekas (ed.): Implementation and Application of Automata (CIAA 2024), LNCS 15015, Springer 2024, 208-220

Deterministic pushdown automata with translucent input letters

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, P. Raucci, M. Wendlandt
In J. D. Day, F. Manea (eds.): Developments in Language Theory (DLT 2024), LNCS 14791, Springer 2024, 203-217

Reversible two-party computations

M. Kutrib, A. Malcher
In Z. Gazdag, S. Iván and 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, G. Vaszil (eds.): Descriptional Complexity of Formal Systems (DCFS 2023), LNCS 13918, Springer 2023, 121-133

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

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

Iterated uniform finite-state transducers on unary languages

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano
In T. Bureš et al. (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. Gwidzalla et al. (eds.): Cellular Automata for Research and Industry (ACRI 2020), LNCS 12599, Springer 2020, 46-55

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

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

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

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

Iterative arrays with finite inter-cell communication

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

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

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

Hierarchies and undecidability results for iterative arrays with sparse communication

A. Malcher
In J. Baetens, M. Kutrib (eds.): Cellular Automata and Discrete Complex Systems (AUTOMATA 2018), LNCS 10875, Springer 2018, 100-112

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

Decidability questions for insertion systems

A. Malcher
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, 165-180

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

Fast one-way cellular automata with reversible Mealy cells

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

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

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

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

Input-driven queue automata with internal transductions

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

Reversible shrinking two-pushdown automata

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

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

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 of Automata and Applications (NCMA 2015), books@ocg.at, Volume 318, Austrian Computer Society 2015, 141-157

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

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

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

Reversible queue automata

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

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, 282-293

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

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

A direct construction of finite state automata for pushdown store languages

V. Geffert, A. Malcher, K. Meckel, C. Mereghetti, B. Palano
In H. Jürgensen, R. Reis (eds.): Descriptional Complexity of Formal Systems (DCFS 2013), LNCS 8031, Springer 2013, 90-101

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

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

Transductions computed by one-dimensional cellular automata

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

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 TCS 2012), 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

One-way reversible multi-head finite automata

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

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

Descriptional complexity of pushdown store languages

A. Malcher, K. Meckel, C. Mereghetti, B. Palano
In M. Kutrib, N. Moreira, R. Reis (eds.): Descriptional Complexity of Formal Systems (DCFS 2012), LNCS 7386, Springer 2012, 209-221

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

Descriptional complexity of two-way pushdown automata with restricted head reversals

A. Malcher, C. Mereghetti, B. Palano
In M. Holzer, M. Kutrib, G. Pighizzini (eds.): Descriptional Complexity of Formal Systems (DCFS 2011), LNCS 6808, Springer 2011, 248-260

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, 2010, 156-167

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

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 size of one-way cellular automata

M. Kutrib, J. Lefèvre, A. Malcher
In N. Fatès, J. Kari, T. Worsch (eds.): International Workshop On Cellular Automata and Discrete Complex Systems (AUTOMATA 2010), DMTCS proc. AL, 2010, 71-90

On the expressive power of FO[+]

C. Choffrut, A. Malcher, C. Mereghetti, B. Palano
In A. Horia Dediu, H. Fernau, C. Martín-Vide (eds.): International Conference on Language and Automata Theory and Applications (LATA 2010), LNCS 6031, Springer 2010, 190-201

Reversible pushdown automata

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

On one-way one-bit O(1)-message cellular automata

M. Kutrib, A. Malcher
In P. P. B. de Oliveira, J. Kari (eds.): International Workshop On Cellular Automata and Discrete Complex Systems (AUTOMATA 2009), ENTCS 252, Elsevier 2009, 77-91

Logical description of structured and XML-languages

A. Malcher, C. Mereghetti, B. Palano
In A. Cherubini, M. Coppo, G. Persiano (eds.): Italian Conference on Theoretical Computer Science (ICTCS 2009), Politecnico di Milano, Milan 2009, 161-167

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), Universität Magdeburg 2009, 211-222

Cellular automata with sparse communication

M. Kutrib, A. Malcher
In S. Maneth (ed.): Implementation and Application of Automata (CIAA 2009), LNCS 5642, Springer 2009, 34-43

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

Sublinearly space bounded iterative arrays

A. Malcher, C. Mereghetti, B. Palano
In E. Csuhaj-Varjú, Z. Ésik (eds.): Automata and Formal Languages (AFL 2008), Hungarian Academy of Sciences, Budapest 2008, 292-301

Descriptional complexity of splicing systems

R. Loos, A. Malcher, D. Wotschke
In V. Geffert, G. Pighizzini (eds.): Descriptional Complexity of Formal Systems (DCFS 2007), Univerzity P. J. Šafárik, Košice 2007, 93-104

Regulated nondeterminism in pushdown automata

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

Real-time reversible iterative arrays

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

Descriptional complexity of bounded context-free languages

A. Malcher, G. Pighizzini
In T. Harju, J. Karhumäki, A. Lepistö (eds.): Developments in Language Theory (DLT 2007), LNCS 4588, Springer 2007, 312-323

Fast reversible language recognition using cellular automata

M. Kutrib, A. Malcher
In R. Loos, S. Z. Fazekas, C. Martín-Vide (eds.): Language and Automata Theory and Applications (LATA 2007), Reports of the Research Group on Mathematical Linguistics, 35/07, Universitat Rovira i Virgili, Tarragona, 2007, 331-342

Fast cellular automata with restricted inter-cell communication: constructions and decidability

M. Kutrib, A. Malcher
In R. Královič, P. Urzyczyn (eds.): Mathematical Foundations of Computer Science 2006 (MFCS 2006), LNCS 4162, Springer 2006, 634-645

Context-dependent nondeterminism for pushdown automata

M. Kutrib, A. Malcher
In O. H. Ibarra, Z. Dang (eds.): Developments in Language Theory (DLT 2006), LNCS 4036, Springer 2006, 133-144

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

On recursive and non-recursive trade-offs between finite-turn pushdown automata

A. Malcher
In C. Mereghetti, B. Palano, G. Pighizzini, D. Wotschke (eds.): Descriptional Complexity of Formal Systems (DCFS 2005), Milan 2005, 215-226

The Boolean closure of linear context-free languages

M. Kutrib, A. Malcher, D. Wotschke
In C. S. Calude, E. Calude, M. J. Dinneen (eds.): Developments in Language Theory (DLT 2004), LNCS 3340, Springer 2004, 184-295

On two-way communication in cellular automata with a fixed number of cells

A. Malcher
In E. Csuhaj-Varjù, C. Kintala, D. Wotschke, G. Vaszil (eds.): Descriptional Complexity of Formal Systems (DCFS 2003), Budapest 2003, 162-173

Minimizing finite automata is computationally hard

A. Malcher
In Z. Ésik, Z. Fülöp (eds.): Developments in Language Theory (DLT 2003), LNCS 2710, Springer 2003, 386-397

On one-way cellular automata with a fixed number of cells

A. Malcher
In J. Dassow, M. Hoeberechts, H. Jürgensen, D. Wotschke (eds.): Descriptional Complexity of Formal Systems (DCFS 2002), London, Canada, 2002, 160-173

Descriptional complexity of cellular automata and decidability questions

A. Malcher
In J. Dassow, D. Wotschke (eds.): Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS 2001), Magdeburg 2001, 123-131



Invited Papers

Cellular automata: from black-and-white to high gloss color

M. Kutrib, A. Malcher
In J. D. Day, F. Manea (eds.): Developments in Language Theory (DLT 2024), LNCS 14791, Springer 2024, 22-36

Cellular automata: communication matters

M. Kutrib, A. Malcher
In L. Levy Patey, E. Pimentel, L. Galeotti, F. Manea (ed.): Computability in Europe (CIE 2024), LNCS 14773, Springer 2024, 32-43

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

Cellular automata: descriptional complexity and decidability

M. Kutrib, A. Malcher
In A. Adamatzky (ed.): Reversibility and Universality (Essays presented to Kenichi Morita on the occasion of his 70th birthday), Emergence, Complexity, and Computation, Vol. 30, Springer 2018, 129-168

Queue automata: foundations and developments

M. Kutrib, A. Malcher, M. Wendlandt
In A. Adamatzky (ed.): Reversibility and Universality (Essays presented to Kenichi Morita on the occasion of his 70th birthday), Emergence, Complexity, and Computation, Vol. 30, Springer 2018, 385-431

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

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, 2010, 13-30

Remembering Chandra Kintala

M. Kappes, A. Malcher, D. Wotschke
In I. McQuillan, G. Pighizzini, B. Trost (eds.): Descriptional Complexity of Formal Systems (DCFS 2010), University of Saskatchewan, Saskatoon, Canada, 2010, 23-37

Multi-head finite automata: characterizations, concepts and open problems

M. Holzer, M. Kutrib, A. Malcher
In T. Neary, D. Woods, A. K. Seda, N. Murphy (eds.): The Complexity of Simple Programs (CSP 2008), Cork University Press, Cork, Ireland, 2008, 117-136

Descriptional complexity and cellular automata

A. Malcher
In H. Leung, G. Pighizzini (eds.): Descriptional Complexity of Formal Systems (DCFS 2006), Las Cruces, USA, 2006, 26-40



Edited Volumes

Special Issue dedicated to Martin Kutrib's 60th birthday

H. Fernau, A. Malcher, G. Pighizzini (Eds.)
Acta Informatica, Volume 58 (4), 2021

Special Issue: Cellular Automata and Discrete Complex Systems (AUTOMATA 2013)

J. Kari, M. Kutrib, A. Malcher (Eds.)
Journal of Cellular Automata, Volume 9 (5-6), 2014

Cellular Automata and Discrete Complex Systems (AUTOMATA 2013)

J. Kari, M. Kutrib, A. Malcher (Eds.)
Lecture Notes in Computer Science, vol. 8155, Springer, 2013

AUTOMATA 2013 - Exploratory Papers

J. Kari, M. Kutrib, A. Malcher (Eds.)
Institut für Informatik, Report 1302, Universität Gießen, 2013

Special Issue: Selected Papers Dedicated to the 65th Birthday of Detlef Wotschke

J. Dassow, A. Malcher (Eds.)
Journal of Automata, Languages and Combinatorics, Volume 14 (1), 2009

18. Theorietag Automaten und Formale Sprachen

M. Holzer, M. Kutrib, A. Malcher (Hrsg.)
Institut für Informatik, Report 0801, Universität Gießen, 2008


  18.02.2025
  Zurück zu A. Malcher