×
Author ID: geffert.viliam Recent zbMATH articles by "Geffert, Viliam"
Published as: Geffert, Viliam; Geffert, V.

Publications by Year

Citations contained in zbMATH Open

61 Publications have been cited 442 times in 281 Documents Cited by Year
Converting two-way nondeterministic unary automata into simpler automata. Zbl 1045.68080
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni
35
2003
Normal forms for phrase-structure grammars. Zbl 0755.68092
Geffert, Viliam
34
1991
Magic numbers in the state hierarchy of finite automata. Zbl 1130.68069
Geffert, Viliam
31
2007
Complementing two-way finite automata. Zbl 1121.68063
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni
30
2007
Nondeterministic computations in sublogarithmic space and space constructibility. Zbl 0762.68022
Geffert, Viliam
21
1991
Context-free-like forms for the phrase-structure grammars. Zbl 0652.68095
Geffert, Viliam
21
1988
Hyper-minimizing minimized deterministic finite state automata. Zbl 1170.68023
Badr, Andrew; Geffert, Viliam; Shipman, Ian
19
2009
More concise representation of regular languages by automata and regular expressions. Zbl 1192.68409
Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
17
2010
A hierarchy that does not collapse: Alternations in low level space. Zbl 0884.68054
Geffert, Viliam
12
1994
Asymptotically efficient in-place merging. Zbl 0939.68160
Geffert, V.; Katajainen, J.; Pasanen, T.
12
2000
Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space. Zbl 0766.68039
Geffert, Viliam
10
1993
Two-way unary automata versus logarithmic space. Zbl 1216.68143
Geffert, Viliam; Pighizzini, Giovanni
9
2011
An alternating hierarchy for finite automata. Zbl 1255.68095
Geffert, Viliam
9
2012
The size-cost of Boolean operations on constant height deterministic pushdown automata. Zbl 1272.68205
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
9
2012
Bridging across the \(\log(n)\) space frontier. Zbl 0917.68077
Geffert, Viliam
9
1998
Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions. Zbl 1055.68068
Geffert, Viliam
9
2003
Classical automata on promise problems. Zbl 1333.68166
Geffert, Viliam; Yakaryılmaz, Abuzer
9
2015
Transforming two-way alternating finite automata to one-way nondeterministic automata. Zbl 1425.68200
Geffert, Viliam; Okhotin, Alexander
8
2014
How to generate languages using only two pairs of parentheses. Zbl 0755.68091
Geffert, Viliam
7
1991
Boolean language operations on nondeterministic automata with a pushdown of constant height. Zbl 1362.68139
Geffert, Viliam; Bednárová, Zuzana; Mereghetti, Carlo; Palano, Beatrice
7
2013
Grammars with context dependency restricted to synchronization. Zbl 0611.68050
Geffert, Viliam
7
1986
Space hierarchy theorem revised. Zbl 1038.68053
Geffert, Viliam
7
2003
Classical automata on promise problems. Zbl 1333.68165
Geffert, Viliam; Yakaryılmaz, Abuzer
7
2014
Removing nondeterminism in constant height pushdown automata. Zbl 1360.68539
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
6
2014
Sublogarithmic bounds on space and reversals. Zbl 0914.68068
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni
6
1998
New results on the minimum amount of useful space. Zbl 1338.68138
Bednárová, Zuzana; Geffert, Viliam; Reinhardt, Klaus; Yakaryilmaz, Abuzer
6
2016
A lower bound for the nondeterministic space complexity of context-free recognition. Zbl 0780.68081
Alt, Helmut; Geffert, Viliam; Mehlhorn, Kurt
5
1992
An in-place sorting with \(O(n \log n)\) comparisons and \(O(n)\) moves. Zbl 1323.68246
Franceschini, Gianni; Geffert, Viliam
5
2005
Pairs of complementary unary languages with “balanced” nondeterministic automata. Zbl 1236.68168
Geffert, Viliam; Pighizzini, Giovanni
5
2012
Magic numbers in the state hierarchy of finite automata. Zbl 1132.68444
Geffert, Viliam
4
2006
A representation of recursively enumerable languages by two homomorphisms and a quotient. Zbl 0664.68075
Geffert, Viliam
4
1988
Boolean language operations on nondeterministic automata with a pushdown of constant height. Zbl 1374.68251
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
4
2017
Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\). Zbl 1298.68134
Geffert, Viliam; Pardubská, Dana
4
2013
Nondeterministic computations in sublogarithmic space and space constructibility. Zbl 0765.68035
Geffert, Viliam
3
1990
Pairs of complementary unary languages with “balanced” nondeterministic automata. Zbl 1283.68195
Geffert, Viliam; Pighizzini, Giovanni
3
2010
A communication hierarchy of parallel computations. Zbl 0902.68074
Geffert, Viliam
3
1998
Deterministic one-way simulation of two-way deterministic finite automata over small alphabets. Zbl 07614739
Geffert, Viliam; Okhotin, Alexander
3
2021
Translation from classical two-way automata to pebble two-way automata. Zbl 1211.68232
Geffert, Viliam; Ištoňová, L’ubomíra
3
2010
A speed-up theorem without tape compression. Zbl 0796.68087
Geffert, Viliam
3
1993
Sublogarithmic \(\Sigma_ 2\)-space is not closed under complement and other separation results. Zbl 0804.68047
Geffert, V.
3
1993
Two-way automata making choices only at the endmarkers. Zbl 1309.68119
Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni
3
2014
Complement for two-way alternating automata. Zbl 1484.68086
Geffert, Viliam
3
2018
Multiway in-place merging. Zbl 1252.68089
Geffert, Viliam; Gajdoš, Jozef
2
2009
Two double-exponential gaps for automata with a limited pushdown. Zbl 1362.68126
Bednárová, Zuzana; Geffert, Viliam
2
2014
Multiway in-place merging. Zbl 1191.68223
Geffert, Viliam; Gajdoš, Jozef
2
2010
Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\). Zbl 1425.68199
Geffert, Viliam
2
2019
Two-way unary automata versus logarithmic space. Zbl 1250.68157
Geffert, Viliam; Pighizzini, Giovanni
2
2010
Input-driven pushdown automata for edit distance neighborhood. Zbl 1534.68087
Geffert, Viliam; Bednárová, Zuzana; Szabari, Alexander
2
2019
Complement for two-way alternating automata. Zbl 1528.68184
Geffert, Viliam; Kapoutsis, Christos A.; Zakzok, Mohammad
2
2021
State complexity of binary coded regular languages. Zbl 07643464
Geffert, Viliam; Pališínová, Dominika; Szabari, Alexander
2
2022
Removing nondeterminism in constant height pushdown automata. Zbl 1304.68092
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
1
2012
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
Bridging across the \(\log (n)\) space frontier. Zbl 1193.68114
Geffert, Viliam
1
1995
Linear-time in-place selection with \(\varepsilon \cdot n\) element moves. Zbl 1119.68061
Geffert, Viliam; Kollár, Ján
1
2006
Two-way automata making choices only at the endmarkers. Zbl 1351.68138
Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni
1
2012
Factoring and testing primes in small space. Zbl 1315.11100
Geffert, Viliam; Pardubská, Dana
1
2013
Speed-up theorem without tape compression. Zbl 0733.68022
Geffert, Viliam
1
1990
Alternating demon space is closed under complement and other simulations for sublogarithmic space. Zbl 1359.68095
Geffert, Viliam
1
2016
Alternating space is closed under complement and other simulations for sublogarithmic space. Zbl 1364.68215
Geffert, Viliam
1
2017
Two double-exponential gaps for automata with a limited pushdown. Zbl 1370.68157
Bednárová, Zuzana; Geffert, Viliam
1
2017
In-place sorting. Zbl 1298.68074
Geffert, Viliam; Gajdoš, Jozef
1
2011
State complexity of binary coded regular languages. Zbl 07643464
Geffert, Viliam; Pališínová, Dominika; Szabari, Alexander
2
2022
Deterministic one-way simulation of two-way deterministic finite automata over small alphabets. Zbl 07614739
Geffert, Viliam; Okhotin, Alexander
3
2021
Complement for two-way alternating automata. Zbl 1528.68184
Geffert, Viliam; Kapoutsis, Christos A.; Zakzok, Mohammad
2
2021
Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\). Zbl 1425.68199
Geffert, Viliam
2
2019
Input-driven pushdown automata for edit distance neighborhood. Zbl 1534.68087
Geffert, Viliam; Bednárová, Zuzana; Szabari, Alexander
2
2019
Complement for two-way alternating automata. Zbl 1484.68086
Geffert, Viliam
3
2018
Boolean language operations on nondeterministic automata with a pushdown of constant height. Zbl 1374.68251
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
4
2017
Alternating space is closed under complement and other simulations for sublogarithmic space. Zbl 1364.68215
Geffert, Viliam
1
2017
Two double-exponential gaps for automata with a limited pushdown. Zbl 1370.68157
Bednárová, Zuzana; Geffert, Viliam
1
2017
New results on the minimum amount of useful space. Zbl 1338.68138
Bednárová, Zuzana; Geffert, Viliam; Reinhardt, Klaus; Yakaryilmaz, Abuzer
6
2016
Alternating demon space is closed under complement and other simulations for sublogarithmic space. Zbl 1359.68095
Geffert, Viliam
1
2016
Classical automata on promise problems. Zbl 1333.68166
Geffert, Viliam; Yakaryılmaz, Abuzer
9
2015
Transforming two-way alternating finite automata to one-way nondeterministic automata. Zbl 1425.68200
Geffert, Viliam; Okhotin, Alexander
8
2014
Classical automata on promise problems. Zbl 1333.68165
Geffert, Viliam; Yakaryılmaz, Abuzer
7
2014
Removing nondeterminism in constant height pushdown automata. Zbl 1360.68539
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
6
2014
Two-way automata making choices only at the endmarkers. Zbl 1309.68119
Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni
3
2014
Two double-exponential gaps for automata with a limited pushdown. Zbl 1362.68126
Bednárová, Zuzana; Geffert, Viliam
2
2014
Boolean language operations on nondeterministic automata with a pushdown of constant height. Zbl 1362.68139
Geffert, Viliam; Bednárová, Zuzana; Mereghetti, Carlo; Palano, Beatrice
7
2013
Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\). Zbl 1298.68134
Geffert, Viliam; Pardubská, Dana
4
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
Factoring and testing primes in small space. Zbl 1315.11100
Geffert, Viliam; Pardubská, Dana
1
2013
An alternating hierarchy for finite automata. Zbl 1255.68095
Geffert, Viliam
9
2012
The size-cost of Boolean operations on constant height deterministic pushdown automata. Zbl 1272.68205
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
9
2012
Pairs of complementary unary languages with “balanced” nondeterministic automata. Zbl 1236.68168
Geffert, Viliam; Pighizzini, Giovanni
5
2012
Removing nondeterminism in constant height pushdown automata. Zbl 1304.68092
Bednárová, Zuzana; Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
1
2012
Two-way automata making choices only at the endmarkers. Zbl 1351.68138
Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni
1
2012
Two-way unary automata versus logarithmic space. Zbl 1216.68143
Geffert, Viliam; Pighizzini, Giovanni
9
2011
In-place sorting. Zbl 1298.68074
Geffert, Viliam; Gajdoš, Jozef
1
2011
More concise representation of regular languages by automata and regular expressions. Zbl 1192.68409
Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice
17
2010
Pairs of complementary unary languages with “balanced” nondeterministic automata. Zbl 1283.68195
Geffert, Viliam; Pighizzini, Giovanni
3
2010
Translation from classical two-way automata to pebble two-way automata. Zbl 1211.68232
Geffert, Viliam; Ištoňová, L’ubomíra
3
2010
Multiway in-place merging. Zbl 1191.68223
Geffert, Viliam; Gajdoš, Jozef
2
2010
Two-way unary automata versus logarithmic space. Zbl 1250.68157
Geffert, Viliam; Pighizzini, Giovanni
2
2010
Hyper-minimizing minimized deterministic finite state automata. Zbl 1170.68023
Badr, Andrew; Geffert, Viliam; Shipman, Ian
19
2009
Multiway in-place merging. Zbl 1252.68089
Geffert, Viliam; Gajdoš, Jozef
2
2009
Magic numbers in the state hierarchy of finite automata. Zbl 1130.68069
Geffert, Viliam
31
2007
Complementing two-way finite automata. Zbl 1121.68063
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni
30
2007
Magic numbers in the state hierarchy of finite automata. Zbl 1132.68444
Geffert, Viliam
4
2006
Linear-time in-place selection with \(\varepsilon \cdot n\) element moves. Zbl 1119.68061
Geffert, Viliam; Kollár, Ján
1
2006
An in-place sorting with \(O(n \log n)\) comparisons and \(O(n)\) moves. Zbl 1323.68246
Franceschini, Gianni; Geffert, Viliam
5
2005
Converting two-way nondeterministic unary automata into simpler automata. Zbl 1045.68080
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni
35
2003
Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions. Zbl 1055.68068
Geffert, Viliam
9
2003
Space hierarchy theorem revised. Zbl 1038.68053
Geffert, Viliam
7
2003
Asymptotically efficient in-place merging. Zbl 0939.68160
Geffert, V.; Katajainen, J.; Pasanen, T.
12
2000
Bridging across the \(\log(n)\) space frontier. Zbl 0917.68077
Geffert, Viliam
9
1998
Sublogarithmic bounds on space and reversals. Zbl 0914.68068
Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni
6
1998
A communication hierarchy of parallel computations. Zbl 0902.68074
Geffert, Viliam
3
1998
Bridging across the \(\log (n)\) space frontier. Zbl 1193.68114
Geffert, Viliam
1
1995
A hierarchy that does not collapse: Alternations in low level space. Zbl 0884.68054
Geffert, Viliam
12
1994
Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space. Zbl 0766.68039
Geffert, Viliam
10
1993
A speed-up theorem without tape compression. Zbl 0796.68087
Geffert, Viliam
3
1993
Sublogarithmic \(\Sigma_ 2\)-space is not closed under complement and other separation results. Zbl 0804.68047
Geffert, V.
3
1993
A lower bound for the nondeterministic space complexity of context-free recognition. Zbl 0780.68081
Alt, Helmut; Geffert, Viliam; Mehlhorn, Kurt
5
1992
Normal forms for phrase-structure grammars. Zbl 0755.68092
Geffert, Viliam
34
1991
Nondeterministic computations in sublogarithmic space and space constructibility. Zbl 0762.68022
Geffert, Viliam
21
1991
How to generate languages using only two pairs of parentheses. Zbl 0755.68091
Geffert, Viliam
7
1991
Nondeterministic computations in sublogarithmic space and space constructibility. Zbl 0765.68035
Geffert, Viliam
3
1990
Speed-up theorem without tape compression. Zbl 0733.68022
Geffert, Viliam
1
1990
Context-free-like forms for the phrase-structure grammars. Zbl 0652.68095
Geffert, Viliam
21
1988
A representation of recursively enumerable languages by two homomorphisms and a quotient. Zbl 0664.68075
Geffert, Viliam
4
1988
Grammars with context dependency restricted to synchronization. Zbl 0611.68050
Geffert, Viliam
7
1986
all top 5

Cited by 252 Authors

39 Geffert, Viliam
21 Pighizzini, Giovanni
20 Okhotin, Alexander
17 Fernau, Henning
17 Mereghetti, Carlo
16 Yakaryılmaz, Abuzer
15 Holzer, Markus
15 Kuppusamy, Lakshmanan
15 Kutrib, Martin
14 Raman, Indhumathi
13 Jirásková, Galina
12 Palano, Beatrice
10 Kapoutsis, Christos A.
10 Malcher, Andreas
9 Csuhaj-Varjú, Erzsébet
9 Salomaa, Kai T.
8 Maletti, Andreas
8 Prigioniero, Luca
7 Masopust, Tomáš
7 Meduna, Alexander
6 Bednárová, Zuzana
6 Dassow, Jürgen
6 Martynova, Olga
6 Vaszil, Gyorgy
5 Hromkovič, Juraj
5 Păun, Gheorghe
5 Say, A. C. Cem
4 Guillon, Bruno
4 Inoue, Katsushi
4 Ito, Akira
4 Pardubská, Dana
4 Vahrenhold, Jan
4 Wendlandt, Matthias
4 Zakzok, Mohammad
3 Badr, Andrew
3 Gainutdinova, Aida
3 Jakobi, Sebastian
3 Jeż, Artur
3 Khadiev, Kamil
3 Královič, Richard
3 Kunc, Michal
3 Mitrana, Victor
3 Nakanishi, Masaki
3 Okubo, Fumiya
3 Schnitger, Georg
3 Selamat, Mohd Hasan
3 Szabari, Alexander
3 Szepietowski, Andrzej
3 Takanami, Itsuo
3 Turaev, Sherzod
3 Verlan, Sergey
2 Bianchi, Maria Paola
2 Bordihn, Henning
2 Bruda, Stefan D.
2 Chan, Timothy Moon-Yew
2 Chen, Jingchao
2 Dimitrijevs, Maksims
2 Freund, Rudolf
2 Gajdoš, Jozef
2 Gawrychowski, Paweł
2 Gruber, Hermann
2 Han, Yo-Sub
2 Ištoňová, L’ubomíra
2 Karhumaki, Juhani
2 Ko, Sang-Ki
2 Kováč, Ivan
2 Královič, Rastislav
2 Křivka, Zbyněk
2 Kupferman, Orna
2 Manea, Florin
2 Martín-Vide, Carlos
2 Mömke, Tobias
2 Oladele, Rufus O.
2 Pališínová, Dominika
2 Petrov, Semyon
2 Popély, Norbert
2 Prūsis, Krišjānis
2 Quernheim, Daniel
2 Rauch, Christian
2 Salomaa, Arto Kustaa
2 Shallit, Jeffrey Outlaw
2 Vihrovs, Jevgēnijs
2 Villagra, Marcos
2 Wild, Sebastian
2 Wilkin, Mary Sarah Ruth
2 Yamakami, Tomoyuki
2 Yokomori, Takashi
2 Yoshinaga, Tsunehiro
2 Yu, Sheng
2 Zan, Jinfeng
2 Zemek, Petr
1 Ablaev, Farid M.
1 Abu, Radi Bader
1 Agadzanyan, Ruben
1 Agrawal, Manindra
1 Akl, Selim G.
1 Alhazov, Artiom
1 Alsaadi, Fuad Eid Salem
1 Anselmo, Marcella
1 Axtmann, Michael
...and 152 more Authors

Citations by Year