Selected Publications


Peer-Reviewed Journal Papers


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


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


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



  04.10.2017
  Zurück zu A. Malcher