Viliam Geffert

According to our database, Viliam Geffert authored at least 66 papers between 1986 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

Binary Coded Unary Regular Languages.

Viliam Geffert

Proceedings of the Implementation and Application of Automata, 2023

2022

Input-driven pushdown automata for edit distance neighborhood.

Viliam Geffert, Zuzana Bednárová, Alexander Szabari

Theor. Comput. Sci., 2022

Improved complement for two-way alternating automata.

Viliam Geffert, Christos A. Kapoutsis, Mohammad Zakzok

Acta Informatica, 2022

State Complexity of Binary Coded Regular Languages.

Viliam Geffert, Dominika Palisínová, Alexander Szabari

Proceedings of the Descriptional Complexity of Formal Systems, 2022

2021

Minimal Size of Counters for (Real-Time) Multicounter Automata.

Viliam Geffert, Zuzana Bednárová

Fundam. Informaticae, 2021

Complement for two-way alternating automata.

Viliam Geffert, Christos A. Kapoutsis, Mohammad Zakzok

Acta Informatica, 2021

Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets.

Viliam Geffert, Alexander Okhotin

Proceedings of the Descriptional Complexity of Formal Systems, 2021

2019

Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).

Viliam Geffert

Theory Comput. Syst., 2019

2018

Minimal Useful Size of Counters for (Real-Time) Multicounter Automata.

Viliam Geffert, Zuzana Bednárová

Proceedings of the Machines, Computations, and Universality - 8th International Conference, 2018

Complement for Two-Way Alternating Automata.

Viliam Geffert

Proceedings of the Computer Science - Theory and Applications, 2018

2017

Boolean language operations on nondeterministic automata with a pushdown of constant height.

Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano

J. Comput. Syst. Sci., 2017

Alternating space is closed under complement and other simulations for sublogarithmic space.

Viliam Geffert

Inf. Comput., 2017

Two double-exponential gaps for automata with a limited pushdown.

Zuzana Bednárová, Viliam Geffert

Inf. Comput., 2017

2016

New Results on the Minimum Amount of Useful Space.

Zuzana Bednárová, Viliam Geffert, Klaus Reinhardt, Abuzer Yakaryilmaz

Int. J. Found. Comput. Sci., 2016

Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space.

Viliam Geffert

Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015

Classical Automata on Promise Problems.

Viliam Geffert, Abuzer Yakaryilmaz

Discret. Math. Theor. Comput. Sci., 2015

2014

Two-way automata making choices only at the endmarkers.

Viliam Geffert, Bruno Guillon, Giovanni Pighizzini

Inf. Comput., 2014

Removing nondeterminism in constant height pushdown automata.

Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Inf. Comput., 2014

Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata.

Viliam Geffert, Alexander Okhotin

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Factoring and testing primes in small space.

Viliam Geffert, Dana Pardubská

RAIRO Theor. Informatics Appl., 2013

Unary Coded NP-Complete Languages in Aspace(log log n).

Viliam Geffert, Dana Pardubská

Int. J. Found. Comput. Sci., 2013

One-way simulation of two-way finite automata over small alphabets.

Viliam Geffert, Alexander Okhotin

Proceedings of the Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13, 2013

A Direct Construction of Finite State Automata for Pushdown Store Languages.

Viliam Geffert, Andreas Malcher, Katja Meckel, Carlo Mereghetti, Beatrice Palano

Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012

An alternating hierarchy for finite automata.

Viliam Geffert

Theor. Comput. Sci., 2012

The size-cost of Boolean operations on constant height deterministic pushdown automata.

Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Theor. Comput. Sci., 2012

Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata.

Viliam Geffert, Giovanni Pighizzini

Algorithmica, 2012

2011

Two-way unary automata versus logarithmic space.

Viliam Geffert, Giovanni Pighizzini

Inf. Comput., 2011

In-Place Sorting.

Viliam Geffert, Jozef Gajdos

Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

2010

Multiway in-place merging.

Viliam Geffert, Jozef Gajdos

Theor. Comput. Sci., 2010

More concise representation of regular languages by automata and regular expressions.

Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Inf. Comput., 2010

One Pebble Versus epsilon * log n Bits.

Viliam Geffert, Giovanni Pighizzini, Carlo Mereghetti

Fundam. Informaticae, 2010

2009

Hyper-minimizing minimized deterministic finite state automata.

Andrew Badr, Viliam Geffert, Ian Shipman

RAIRO Theor. Informatics Appl., 2009

Translation from Classical Two-Way Automata to Pebble Two-Way Automata

Viliam Geffert, Lubomíra Istonová

Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009

One Pebble Versus log(n) Bits.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Proceedings of the Workshop on Non-Classical Models for Automata and Applications - NCMA 2009, Wroclaw, Poland, August 31, 2009

2008

Preface.

Viliam Geffert, Giovanni Pighizzini

Int. J. Found. Comput. Sci., 2008

Multiway blockwise in-place merging.

Viliam Geffert, Jozef Gajdos

Proceedings of the Conference on Theory and Practice of Information Technologies, 2008

Hyper-Minimizing Minimized Deterministic Automata.

Viliam Geffert, Andrew Badr, Ian Shipman

Proceedings of the Automata and Formal Languages, 12th International Conference, 2008

2007

State Hierarchy for One-Way Finite Automata.

Viliam Geffert

J. Autom. Lang. Comb., 2007

Complementing two-way finite automata.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Inf. Comput., 2007

Magic numbers in the state hierarchy of finite automata.

Viliam Geffert

Inf. Comput., 2007

2006

Conversion of regular expressions into realtime automata.

Viliam Geffert, Lubomíra Istonová

RAIRO Theor. Informatics Appl., 2006

Linear-Time In-Place Selection with epsilon.n Element Moves.

Ján Kollár, Viliam Geffert

Comput. Artif. Intell., 2006

2005

An in-place sorting with <i>O</i>(<i>n</i>log <i>n</i>) comparisons and <i>O</i>(<i>n</i>) moves.

Gianni Franceschini, Viliam Geffert

J. ACM, 2005

(Non)determinism and the Size of One-Way Finite Automata.

Viliam Geffert

Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30, 2005

2003

Converting two-way nondeterministic unary automata into simpler automata.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

Theor. Comput. Sci., 2003

Space hierarchy theorem revised.

Viliam Geffert

Theor. Comput. Sci., 2003

Translation of binary regular expressions into nondeterministic ε-free automata with transitions.

Viliam Geffert

J. Comput. Syst. Sci., 2003

An In-Place Sorting with O(n log n) Comparisons and O(n) Moves.

Gianni Franceschini, Viliam Geffert

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Refinement of the Alternating Space Hierarchy.

Viliam Geffert, Norbert Popély

Comput. Artif. Intell., 2002

2000

Asymptotically efficient in-place merging.

Viliam Geffert, Jyrki Katajainen, Tomi Pasanen

Theor. Comput. Sci., 2000

A variant of inductive counting.

Viliam Geffert

Theor. Comput. Sci., 2000

A space lower bound for acceptance by one-way II₂-alternating machines.

Viliam Geffert, Norbert Popély

RAIRO Theor. Informatics Appl., 2000

1998

A Communication Hierarchy of Parallel Computations.

Viliam Geffert

Theor. Comput. Sci., 1998

Sublogarithmic Bounds on Space and Reversals.

Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini

SIAM J. Comput., 1998

Bridging Across the log(n) Space Frontier.

Viliam Geffert

Inf. Comput., 1998

1994

A Hierarchy That Does Not Collapse: Alternations in Low Level Space.

Viliam Geffert

RAIRO Theor. Informatics Appl., 1994

1993

A Speed-Up Theorem Without Tape Compression.

Viliam Geffert

Theor. Comput. Sci., 1993

Tally Versions of the Savitch and Immerman-Szelepcsenyi Theorems for Sublogarithmic Space.

Viliam Geffert

SIAM J. Comput., 1993

Sublogarithmic Sigma₂-Space is not Closed under Complement and Other Separation Results.

Viliam Geffert

RAIRO Theor. Informatics Appl., 1993

1992

A Lower Bound for the Nondeterministic Space Complexity of Context-Free Recognition.

Helmut Alt, Viliam Geffert, Kurt Mehlhorn

Inf. Process. Lett., 1992

1991

Nondeterministic Computations in Sublogarithmic Space and Space Constructibility.

Viliam Geffert

SIAM J. Comput., 1991

Normal forms for phrase-structure grammars.

Viliam Geffert

RAIRO Theor. Informatics Appl., 1991

How to Generate Languages Using Only Two Pairs of Parentheses.

Viliam Geffert

J. Inf. Process. Cybern., 1991

1988

A Representation of Recursively Enumerable Languages by Two Homomorphisms and a Quotient.

Viliam Geffert

Theor. Comput. Sci., 1988

Context-Free-Like Forms for the Phrase-Structure Grammars.

Viliam Geffert

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1986

Grammars with Context Dependency Restricted to Synchronization.

Viliam Geffert

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986