Viliam Geffert

According to our database1, Viliam Geffert authored at least 66 papers between 1986 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
State complexity of binary coded regular languages.
Theor. Comput. Sci., 2024

2023
Binary Coded Unary Regular Languages.
Proceedings of the Implementation and Application of Automata, 2023

2022
Input-driven pushdown automata for edit distance neighborhood.
Theor. Comput. Sci., 2022

Improved complement for two-way alternating automata.
Acta Informatica, 2022

2021
Minimal Size of Counters for (Real-Time) Multicounter Automata.
Fundam. Informaticae, 2021

Complement for two-way alternating automata.
Acta Informatica, 2021

Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets.
Proceedings of the Descriptional Complexity of Formal Systems, 2021

2019
Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).
Theory Comput. Syst., 2019

2018
Minimal Useful Size of Counters for (Real-Time) Multicounter Automata.
Proceedings of the Machines, Computations, and Universality - 8th International Conference, 2018

Complement for Two-Way Alternating Automata.
Proceedings of the Computer Science - Theory and Applications, 2018

2017
Boolean language operations on nondeterministic automata with a pushdown of constant height.
J. Comput. Syst. Sci., 2017

Alternating space is closed under complement and other simulations for sublogarithmic space.
Inf. Comput., 2017

Two double-exponential gaps for automata with a limited pushdown.
Inf. Comput., 2017

2016
New Results on the Minimum Amount of Useful Space.
Int. J. Found. Comput. Sci., 2016

Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space.
Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2014
Two-way automata making choices only at the endmarkers.
Inf. Comput., 2014

Removing nondeterminism in constant height pushdown automata.
Inf. Comput., 2014

Classical Automata on Promise Problems.
Electron. Colloquium Comput. Complex., 2014

Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013
Factoring and testing primes in small space.
RAIRO Theor. Informatics Appl., 2013

Unary Coded NP-Complete Languages in Aspace(log log n).
Int. J. Found. Comput. Sci., 2013

One-way simulation of two-way finite automata over small alphabets.
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.
Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012
An alternating hierarchy for finite automata.
Theor. Comput. Sci., 2012

The size-cost of Boolean operations on constant height deterministic pushdown automata.
Theor. Comput. Sci., 2012

Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata.
Algorithmica, 2012

2011
Two-way unary automata versus logarithmic space.
Inf. Comput., 2011

In-Place Sorting.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

2010
Multiway in-place merging.
Theor. Comput. Sci., 2010

More concise representation of regular languages by automata and regular expressions.
Inf. Comput., 2010

One Pebble Versus epsilon * log n Bits.
Fundam. Informaticae, 2010

2009
Hyper-minimizing minimized deterministic finite state automata.
RAIRO Theor. Informatics Appl., 2009

Translation from Classical Two-Way Automata to Pebble Two-Way Automata
Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009

One Pebble Versus log(n) Bits.
Proceedings of the Workshop on Non-Classical Models for Automata and Applications - NCMA 2009, Wroclaw, Poland, August 31, 2009

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

Multiway blockwise in-place merging.
Proceedings of the Conference on Theory and Practice of Information Technologies, 2008

Hyper-Minimizing Minimized Deterministic Automata.
Proceedings of the Automata and Formal Languages, 12th International Conference, 2008

2007
State Hierarchy for One-Way Finite Automata.
J. Autom. Lang. Comb., 2007

Complementing two-way finite automata.
Inf. Comput., 2007

Magic numbers in the state hierarchy of finite automata.
Inf. Comput., 2007

2006
Conversion of regular expressions into realtime automata.
RAIRO Theor. Informatics Appl., 2006

Linear-Time In-Place Selection with epsilon.n Element Moves.
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.
J. ACM, 2005

(Non)determinism and the Size of One-Way Finite Automata.
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.
Theor. Comput. Sci., 2003

Space hierarchy theorem revised.
Theor. Comput. Sci., 2003

Translation of binary regular expressions into nondeterministic ε-free automata with transitions.
J. Comput. Syst. Sci., 2003

An In-Place Sorting with O(n log n) Comparisons and O(n) Moves.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Refinement of the Alternating Space Hierarchy.
Comput. Artif. Intell., 2002

2000
Asymptotically efficient in-place merging.
Theor. Comput. Sci., 2000

A variant of inductive counting.
Theor. Comput. Sci., 2000

A space lower bound for acceptance by one-way II<sub>2</sub>-alternating machines.
RAIRO Theor. Informatics Appl., 2000

1998
A Communication Hierarchy of Parallel Computations.
Theor. Comput. Sci., 1998

Sublogarithmic Bounds on Space and Reversals.
SIAM J. Comput., 1998

Bridging Across the log(n) Space Frontier.
Inf. Comput., 1998

1994
A Hierarchy That Does Not Collapse: Alternations in Low Level Space.
RAIRO Theor. Informatics Appl., 1994

1993
A Speed-Up Theorem Without Tape Compression.
Theor. Comput. Sci., 1993

Tally Versions of the Savitch and Immerman-Szelepcsenyi Theorems for Sublogarithmic Space.
SIAM J. Comput., 1993

Sublogarithmic Sigma<sub>2</sub>-Space is not Closed under Complement and Other Separation Results.
RAIRO Theor. Informatics Appl., 1993

1992
A Lower Bound for the Nondeterministic Space Complexity of Context-Free Recognition.
Inf. Process. Lett., 1992

1991
Nondeterministic Computations in Sublogarithmic Space and Space Constructibility.
SIAM J. Comput., 1991

Normal forms for phrase-structure grammars.
RAIRO Theor. Informatics Appl., 1991

How to Generate Languages Using Only Two Pairs of Parentheses.
J. Inf. Process. Cybern., 1991

1988
A Representation of Recursively Enumerable Languages by Two Homomorphisms and a Quotient.
Theor. Comput. Sci., 1988

Context-Free-Like Forms for the Phrase-Structure Grammars.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1986
Grammars with Context Dependency Restricted to Synchronization.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986


  Loading...