Viliam Geffert

Dominika Palisínová

Juraj Sebej

Int. J. Found. Comput. Sci., 2025

Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2025

2023

Binary Coded Unary Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2023

2022

Improved complement for two-way alternating automata.

[BibT_eX]

[DOI]

Christos A. Kapoutsis

Mohammad Zakzok

Acta Informatica, 2022

State Complexity of Binary Coded Regular Languages.

[BibT_eX]

[DOI]

Dominika Palisínová

Alexander Szabari

Proceedings of the Descriptional Complexity of Formal Systems, 2022

2021

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

[BibT_eX]

[DOI]

Fundam. Informaticae, 2021

Complement for two-way alternating automata.

[BibT_eX]

[DOI]

Christos A. Kapoutsis

Mohammad Zakzok

Acta Informatica, 2021

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

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2021

2019

Input-Driven Pushdown Automata for Edit Distance Neighborhood.

[BibT_eX]

[DOI]

Alexander Szabari

Proceedings of the Developments in Language Theory - 23rd International Conference, 2019

2018

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

[BibT_eX]

[DOI]

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

Complement for Two-Way Alternating Automata.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

2017

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

[BibT_eX]

[DOI]

Inf. Comput., 2017

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

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2017

2016

New Results on the Minimum Amount of Useful Space.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

2014

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Two Double-Exponential Gaps for Automata with a Limited Pushdown.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2014

Classical Automata on Promise Problems.

[BibT_eX]

[DOI]

Abuzer Yakaryilmaz

Proceedings of the Descriptional Complexity of Formal Systems, 2014

2013

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

[BibT_eX]

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.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2013

Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2013

2012

Two-Way Automata Making Choices Only at the Endmarkers.

[BibT_eX]

[DOI]

Bruno Guillon

Proceedings of the Language and Automata Theory and Applications, 2012

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

[BibT_eX]

[DOI]

Dana Pardubská

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

Removing Nondeterminism in Constant Height Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2012

2011

In-Place Sorting.

[BibT_eX]

[DOI]

Jozef Gajdos

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

An Alternating Hierarchy for Finite Automata.

[BibT_eX]

Proceedings of the Third Workshop on Non-Classical Models for Automata and Applications - NCMA 2011, Milan, Italy, July 18, 2011

The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2011

2010

Translation from classical two-way automata to pebble two-way automata.

[BibT_eX]

[DOI]

Lubomíra Istonová

RAIRO Theor. Informatics Appl., 2010

One Pebble Versus epsilon * log n Bits.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2010

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

[BibT_eX]

[DOI]

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Two-Way Unary Automata versus Logarithmic Space.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009

Hyper-minimizing minimized deterministic finite state automata.

[BibT_eX]

[DOI]

Andrew Badr

Ian Shipman

RAIRO Theor. Informatics Appl., 2009

Factoring and Testing Primes in Small Space.

[BibT_eX]

[DOI]

Dana Pardubská

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

One Pebble Versus log(n) Bits.

[BibT_eX]

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

Multiway In-Place Merging.

[BibT_eX]

[DOI]

Jozef Gajdos

Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

2008

Preface.

[BibT_eX]

[DOI]

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

Multiway blockwise in-place merging.

[BibT_eX]

[DOI]

Jozef Gajdos

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

More Concise Representation of Regular Languages by Automata and Regular Expressions.

[BibT_eX]

[DOI]

Beatrice Palano

Proceedings of the Developments in Language Theory, 12th International Conference, 2008

Hyper-Minimizing Minimized Deterministic Automata.

[BibT_eX]

Andrew Badr

Ian Shipman

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

2007

State Hierarchy for One-Way Finite Automata.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2007

2006

Conversion of regular expressions into realtime automata.

[BibT_eX]

[DOI]

Lubomíra Istonová

RAIRO Theor. Informatics Appl., 2006

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

[BibT_eX]

[DOI]

Ján Kollár

Comput. Artif. Intell., 2006

Magic Numbers in the State Hierarchy of Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005

An in-place sorting with O(nlog n) comparisons and O(n) moves.

[BibT_eX]

[DOI]

Gianni Franceschini

J. ACM, 2005

Complementing Two-Way Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 9th International Conference, 2005

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

[BibT_eX]

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

2003

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

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

[BibT_eX]

[DOI]

Gianni Franceschini

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

2002

Refinement of the Alternating Space Hierarchy.

[BibT_eX]

[DOI]

Norbert Popély

Comput. Artif. Intell., 2002

2001

Converting Two-Way Nondeterministic Unary Automata into Simpler Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Space Hierarchy Theorem Revised.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000

Asymptotically efficient in-place merging.

[BibT_eX]

[DOI]

Jyrki Katajainen

Tomi Pasanen

Theor. Comput. Sci., 2000

A variant of inductive counting.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

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

[BibT_eX]

[DOI]

Norbert Popély

RAIRO Theor. Informatics Appl., 2000

1998

A Communication Hierarchy of Parallel Computations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Sublogarithmic Bounds on Space and Reversals.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

1995

Bridging Across the log(n) Space Frontier.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994

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

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1994

1993

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

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

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

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1993

1992

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

[BibT_eX]

[DOI]

Helmut Alt

Kurt Mehlhorn

Inf. Process. Lett., 1992

1991

Normal forms for phrase-structure grammars.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1991

How to Generate Languages Using Only Two Pairs of Parentheses.

[BibT_eX]

J. Inf. Process. Cybern., 1991

1990

Speed-Up Theorem Without Tape Compression.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Nondeterministic Computations in Sublogarithmic Space and Space Constructibility.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1988

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1988

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1986

Grammars with Context Dependency Restricted to Synchronization.

[BibT_eX]

[DOI]