×

zbMATH — the first resource for mathematics

Malcher, Andreas

Compute Distance To:
Author ID: malcher.andreas Recent zbMATH articles by "Malcher, Andreas"
Published as: Malcher, Andreas
External Links: MGP · Wikidata
Documents Indexed: 94 Publications since 2002, including 1 Book

Publications by Year

Citations contained in zbMATH

59 Publications have been cited 215 times in 112 Documents Cited by Year
Descriptional complexity of machines with limited resources. Zbl 1258.68058
Goldstine, Jonathan; Kappes, Martin; Kintala, Chandra M. R.; Leung, Hing; Malcher, Andreas; Wotschke, Detlef
27
2002
Complexity of multi-head finite automata: origins and directions. Zbl 1207.68188
Holzer, Markus; Kutrib, Martin; Malcher, Andreas
19
2011
Reversible pushdown automata. Zbl 1250.68166
Kutrib, Martin; Malcher, Andreas
14
2012
Descriptional complexity of cellular automata and decidability questions. Zbl 1095.68611
Malcher, Andreas
11
2002
Fast reversible language recognition using cellular automata. Zbl 1154.68082
Kutrib, Martin; Malcher, Andreas
9
2008
Minimizing finite automata is computationally hard. Zbl 1071.68047
Malcher, Andreas
8
2004
One-way reversible multi-head finite automata. Zbl 06514778
Kutrib, Martin; Malcher, Andreas
7
2013
Finite turns and the regular closure of linear context-free languages. Zbl 1123.68062
Kutrib, Martin; Malcher, Andreas
7
2007
Deterministic input-driven queue automata: finite turns, decidability, and closure properties. Zbl 1312.68122
Kutrib, Martin; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice; Wendlandt, Matthias
5
2015
Descriptional complexity of two-way pushdown automata with restricted head reversals. Zbl 1276.68094
Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
5
2012
Real-time reversible iterative arrays. Zbl 1183.68345
Kutrib, Martin; Malcher, Andreas
5
2010
The Boolean closure of linear context-free languages. Zbl 1144.68035
Kutrib, Martin; Malcher, Andreas; Wotschke, Detlef
5
2008
Descriptional complexity of bounded context-free languages. Zbl 1202.68233
Malcher, Andreas; Pighizzini, Giovanni
5
2007
A hierarchy of fast reversible Turing machines. Zbl 06631928
Axelsen, Holger Bock; Jakobi, Sebastian; Kutrib, Martin; Malcher, Andreas
4
2015
Fast iterative arrays with restricted inter-cell communication: constructions and decidability. Zbl 1132.68456
Kutrib, Martin; Malcher, Andreas
4
2006
One-way reversible multi-head finite automata. Zbl 1371.68156
Kutrib, Martin; Malcher, Andreas
3
2017
Tinput-driven pushdown automata. Zbl 1415.68135
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
3
2015
Real-time reversible one-way cellular automata. Zbl 1432.68282
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
3
2015
Descriptional complexity of bounded context-free languages. Zbl 1358.68173
Malcher, Andreas; Pighizzini, Giovanni
3
2013
First-order logics: some characterizations and closure properties. Zbl 1279.68143
Choffrut, Christian; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
3
2012
On the computational capacity of parallel communicating finite automata. Zbl 1279.68133
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
3
2012
Descriptional complexity of splicing systems. Zbl 1156.68032
Loos, Remco; Malcher, Andreas; Wotschke, Detlef
3
2008
When Church-Rosser becomes context free. Zbl 1183.68344
Kutrib, Martin; Malcher, Andreas
3
2007
On recursive and non-recursive trade-offs between finite-turn pushdown automata. Zbl 1149.68394
Malcher, Andreas
3
2007
On two-way communication in cellular automata with a fixed number of cells. Zbl 1078.68101
Malcher, Andreas
3
2005
Tinput-driven pushdown, counter, and stack automata. Zbl 1378.68107
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2017
Reversible queue automata. Zbl 1374.68261
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Boosting reversible pushdown machines by preprocessing. Zbl 06610599
Axelsen, Holger Bock; Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Set automata. Zbl 1352.68134
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Input-driven queue automata with internal transductions. Zbl 1443.68090
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Simulations of unary one-way multi-head finite automata. Zbl 1320.68112
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2014
Head and state hierarchies for unary multi-head finite automata. Zbl 1304.68110
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2014
One-dimensional cellular automaton transducers. Zbl 1302.68195
Kutrib, Martin; Malcher, Andreas
2
2013
Size of unary one-way multi-head finite automata. Zbl 1304.68109
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2013
Input-driven stack automata. Zbl 1362.68127
Bensch, Suna; Holzer, Markus; Kutrib, Martin; Malcher, Andreas
2
2012
Undecidability and hierarchy results for parallel communicating finite automata. Zbl 1252.68165
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
2
2011
Sublinearly space bounded iterative arrays. Zbl 1207.68215
Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
2
2010
Cellular automata with sparse communication. Zbl 1207.68214
Kutrib, Martin; Malcher, Andreas
2
2010
Reversible pushdown automata. Zbl 1284.68356
Kutrib, Martin; Malcher, Andreas
2
2010
Context-dependent nondeterminism for pushdown automata. Zbl 1111.68060
Kutrib, Martin; Malcher, Andreas
2
2007
On one-way cellular automata with a fixed number of cells. Zbl 1111.68524
Malcher, Andreas
2
2003
Queue automata: foundations and developments. Zbl 1434.68274
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2018
Diving into the queue. Zbl 1423.68243
Beier, Simon; Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2018
Iterative arrays with set storage. Zbl 1432.68231
Kutrib, Martin; Malcher, Andreas
1
2017
Reversible shrinking two-pushdown automata. Zbl 1443.68080
Axelsen, Holger Bock; Holzer, Markus; Kutrib, Martin; Malcher, Andreas
1
2016
Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities. Zbl 1338.68141
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
1
2015
Shrinking one-way cellular automata. Zbl 1432.68283
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2015
Stateless one-way multi-head finite automata with pebbles. Zbl 1318.68109
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2014
A direct construction of finite state automata for pushdown store languages. Zbl 1388.68171
Geffert, Viliam; Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice
1
2013
Descriptional complexity of pushdown store languages. Zbl 1322.68124
Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice
1
2012
The size impact of little iterative array resources. Zbl 1280.68130
Kutrib, Martin; Malcher, Andreas
1
2012
States and heads do count for unary multi-head finite automata. Zbl 1370.68183
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2012
Cellular automata with limited inter-cell bandwidth. Zbl 1216.68174
Kutrib, Martin; Malcher, Andreas
1
2011
The size of one-way cellular automata. Zbl 1323.68393
Kutrib, Martin; Lefèvre, Jonas; Malcher, Andreas
1
2010
On the expressive power of FO[+]. Zbl 1284.68343
Choffrut, Christian; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
1
2010
On one-way one-bit \(O\) (one)-message cellular automata. Zbl 1338.68184
Kutrib, Martin; Malcher, Andreas
1
2009
Regulated nondeterminism in pushdown automata. Zbl 1194.68142
Kutrib, Martin; Malcher, Andreas; Werlein, Larissa
1
2009
Cellular automata with sparse communication. Zbl 1248.68343
Kutrib, Martin; Malcher, Andreas
1
2009
On the computational capacity of parallel communicating finite automata. Zbl 1161.68513
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
1
2008
Queue automata: foundations and developments. Zbl 1434.68274
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2018
Diving into the queue. Zbl 1423.68243
Beier, Simon; Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2018
One-way reversible multi-head finite automata. Zbl 1371.68156
Kutrib, Martin; Malcher, Andreas
3
2017
Tinput-driven pushdown, counter, and stack automata. Zbl 1378.68107
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2017
Iterative arrays with set storage. Zbl 1432.68231
Kutrib, Martin; Malcher, Andreas
1
2017
Reversible queue automata. Zbl 1374.68261
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Boosting reversible pushdown machines by preprocessing. Zbl 06610599
Axelsen, Holger Bock; Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Set automata. Zbl 1352.68134
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Input-driven queue automata with internal transductions. Zbl 1443.68090
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2016
Reversible shrinking two-pushdown automata. Zbl 1443.68080
Axelsen, Holger Bock; Holzer, Markus; Kutrib, Martin; Malcher, Andreas
1
2016
Deterministic input-driven queue automata: finite turns, decidability, and closure properties. Zbl 1312.68122
Kutrib, Martin; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice; Wendlandt, Matthias
5
2015
A hierarchy of fast reversible Turing machines. Zbl 06631928
Axelsen, Holger Bock; Jakobi, Sebastian; Kutrib, Martin; Malcher, Andreas
4
2015
Tinput-driven pushdown automata. Zbl 1415.68135
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
3
2015
Real-time reversible one-way cellular automata. Zbl 1432.68282
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
3
2015
Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities. Zbl 1338.68141
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
1
2015
Shrinking one-way cellular automata. Zbl 1432.68283
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2015
Simulations of unary one-way multi-head finite automata. Zbl 1320.68112
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2014
Head and state hierarchies for unary multi-head finite automata. Zbl 1304.68110
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2014
Stateless one-way multi-head finite automata with pebbles. Zbl 1318.68109
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2014
One-way reversible multi-head finite automata. Zbl 06514778
Kutrib, Martin; Malcher, Andreas
7
2013
Descriptional complexity of bounded context-free languages. Zbl 1358.68173
Malcher, Andreas; Pighizzini, Giovanni
3
2013
One-dimensional cellular automaton transducers. Zbl 1302.68195
Kutrib, Martin; Malcher, Andreas
2
2013
Size of unary one-way multi-head finite automata. Zbl 1304.68109
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
2
2013
A direct construction of finite state automata for pushdown store languages. Zbl 1388.68171
Geffert, Viliam; Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice
1
2013
Reversible pushdown automata. Zbl 1250.68166
Kutrib, Martin; Malcher, Andreas
14
2012
Descriptional complexity of two-way pushdown automata with restricted head reversals. Zbl 1276.68094
Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
5
2012
First-order logics: some characterizations and closure properties. Zbl 1279.68143
Choffrut, Christian; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
3
2012
On the computational capacity of parallel communicating finite automata. Zbl 1279.68133
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
3
2012
Input-driven stack automata. Zbl 1362.68127
Bensch, Suna; Holzer, Markus; Kutrib, Martin; Malcher, Andreas
2
2012
Descriptional complexity of pushdown store languages. Zbl 1322.68124
Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice
1
2012
The size impact of little iterative array resources. Zbl 1280.68130
Kutrib, Martin; Malcher, Andreas
1
2012
States and heads do count for unary multi-head finite automata. Zbl 1370.68183
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
1
2012
Complexity of multi-head finite automata: origins and directions. Zbl 1207.68188
Holzer, Markus; Kutrib, Martin; Malcher, Andreas
19
2011
Undecidability and hierarchy results for parallel communicating finite automata. Zbl 1252.68165
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
2
2011
Cellular automata with limited inter-cell bandwidth. Zbl 1216.68174
Kutrib, Martin; Malcher, Andreas
1
2011
Real-time reversible iterative arrays. Zbl 1183.68345
Kutrib, Martin; Malcher, Andreas
5
2010
Sublinearly space bounded iterative arrays. Zbl 1207.68215
Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
2
2010
Cellular automata with sparse communication. Zbl 1207.68214
Kutrib, Martin; Malcher, Andreas
2
2010
Reversible pushdown automata. Zbl 1284.68356
Kutrib, Martin; Malcher, Andreas
2
2010
The size of one-way cellular automata. Zbl 1323.68393
Kutrib, Martin; Lefèvre, Jonas; Malcher, Andreas
1
2010
On the expressive power of FO[+]. Zbl 1284.68343
Choffrut, Christian; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice
1
2010
On one-way one-bit \(O\) (one)-message cellular automata. Zbl 1338.68184
Kutrib, Martin; Malcher, Andreas
1
2009
Regulated nondeterminism in pushdown automata. Zbl 1194.68142
Kutrib, Martin; Malcher, Andreas; Werlein, Larissa
1
2009
Cellular automata with sparse communication. Zbl 1248.68343
Kutrib, Martin; Malcher, Andreas
1
2009
Fast reversible language recognition using cellular automata. Zbl 1154.68082
Kutrib, Martin; Malcher, Andreas
9
2008
The Boolean closure of linear context-free languages. Zbl 1144.68035
Kutrib, Martin; Malcher, Andreas; Wotschke, Detlef
5
2008
Descriptional complexity of splicing systems. Zbl 1156.68032
Loos, Remco; Malcher, Andreas; Wotschke, Detlef
3
2008
On the computational capacity of parallel communicating finite automata. Zbl 1161.68513
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas
1
2008
Finite turns and the regular closure of linear context-free languages. Zbl 1123.68062
Kutrib, Martin; Malcher, Andreas
7
2007
Descriptional complexity of bounded context-free languages. Zbl 1202.68233
Malcher, Andreas; Pighizzini, Giovanni
5
2007
When Church-Rosser becomes context free. Zbl 1183.68344
Kutrib, Martin; Malcher, Andreas
3
2007
On recursive and non-recursive trade-offs between finite-turn pushdown automata. Zbl 1149.68394
Malcher, Andreas
3
2007
Context-dependent nondeterminism for pushdown automata. Zbl 1111.68060
Kutrib, Martin; Malcher, Andreas
2
2007
Fast iterative arrays with restricted inter-cell communication: constructions and decidability. Zbl 1132.68456
Kutrib, Martin; Malcher, Andreas
4
2006
On two-way communication in cellular automata with a fixed number of cells. Zbl 1078.68101
Malcher, Andreas
3
2005
Minimizing finite automata is computationally hard. Zbl 1071.68047
Malcher, Andreas
8
2004
On one-way cellular automata with a fixed number of cells. Zbl 1111.68524
Malcher, Andreas
2
2003
Descriptional complexity of machines with limited resources. Zbl 1258.68058
Goldstine, Jonathan; Kappes, Martin; Kintala, Chandra M. R.; Leung, Hing; Malcher, Andreas; Wotschke, Detlef
27
2002
Descriptional complexity of cellular automata and decidability questions. Zbl 1095.68611
Malcher, Andreas
11
2002
all top 5

Cited by 106 Authors

38 Kutrib, Martin
31 Malcher, Andreas
13 Wendlandt, Matthias
11 Pighizzini, Giovanni
9 Holzer, Markus
9 Salomaa, Kai T.
8 Mereghetti, Carlo
7 Geffert, Viliam
7 Palano, Beatrice
5 Bednárová, Zuzana
4 Axelsen, Holger Bock
4 Okhotin, Alexander
4 Otto, Friedrich
4 Pradella, Matteo
4 Schmid, Markus L.
3 Crespi Reghizzi, Stefano
3 Fernau, Henning
3 Mandrioli, Dino
3 Mitrana, Victor
2 Castellanos, Juan
2 Csuhaj-Varjú, Erzsébet
2 Ibarra, Oscar H.
2 Jirásková, Galina
2 Kappes, Martin
2 Kuppusamy, Lakshmanan
2 Lavado, Giovanna Janet
2 Lonati, Violetta
2 Martens, Wim
2 Palioudakis, Alexandros
2 Piao, Xiaoxue
2 Raman, Indhumathi
2 Reidenbach, Daniel
2 Smith, Tim A.
2 Wotschke, Detlef
1 Akl, Selim G.
1 Arroyo, Fernando
1 Beier, Simon
1 Bhatia, Amandeep Singh
1 Björklund, Henrik
1 Bordihn, Henning
1 Broda, Sabine
1 Carle, Benjamin
1 Chatterjee, Kingshuk
1 Cho, Da-Jung
1 Czech, Łukasz
1 Dassow, Jürgen
1 Domaratzki, Michael
1 Droste, Manfred
1 Dück, Stefan
1 Ďuriš, Pavol
1 Early, Diarmuid
1 Freydenberger, Dominik D.
1 Gao, Ang
1 Gauwin, Olivier
1 Glück, Robert
1 Goč, Daniel
1 Han, Yo-Sub
1 Herrmann, Andrea
1 Jakobi, Sebastian
1 Kapoutsis, Christos A.
1 Keeler, Chris
1 Ko, Sang-Ki
1 Královič, Rastislav
1 Kumar, Ajay
1 Kunc, Michal
1 Kuusisto, Antti
1 Kwee, Kent
1 Loos, Remco
1 Machiavelo, António
1 Margenstern, Maurice
1 McQuillan, Ian
1 Mera, Filippo
1 Modanese, Augusto
1 Moreira, Nelma
1 Morita, Kenichi
1 Muscholl, Anca
1 Narendran, Paliath
1 Niehren, Joachim
1 Nießner, Frank
1 Okubo, Fumiya
1 Panella, Federica
1 Paramasivan, Meenakshi
1 Pardubská, Dana
1 Păun, Gheorghe
1 Petre, Ion
1 Prigioniero, Luca
1 Raskin, Michael A.
1 Ravikumar, Bala
1 Ray, Kumar Sankar
1 Reis, Rogério
1 Reiter, Fabian
1 Rogojin, Vladimir
1 Rogozhin, Yurii
1 San Pietro, Pierluigi L.
1 Sánchez-Couso, José-Ramón
1 Santos, Eugenio
1 Schellekens, Michel P.
1 Seki, Shinnosuke
1 Subramani, Krishnan
1 Tauras, C.
...and 6 more Authors

Citations by Year

Wikidata Timeline