Pavol Duris

Rastislav Královic

Dana Pardubská

J. Comput. Syst. Sci., 2020

Randomization in Non-Uniform Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2018

Determinism and Nondeterminism in Finite Automata with Advice.

[BibT_eX]

[DOI]

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2012

A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable.

[BibT_eX]

[DOI]

Marek Kosta

Electron. Colloquium Comput. Complex., 2011

On Computational Power of Partially Blind Automata.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Flip-pushdown automata: nondeterministic ε-moves can be removed.

[BibT_eX]

[DOI]

Marek Kosta

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

2004

On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata.

[BibT_eX]

[DOI]

Katsushi Inoue

J. Comput. Syst. Sci., 2004

On multi-partition communication complexity.

[BibT_eX]

[DOI]

Inf. Comput., 2004

Multiparty communication complexity and very hard functions.

[BibT_eX]

[DOI]

Inf. Comput., 2004

2001

On Multipartition Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the STACS 2001, 2001

On the Computational Complexity of Infinite Words.

[BibT_eX]

[DOI]

Ján Manuch

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition.

[BibT_eX]

[DOI]

Katsushi Inoue

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1998

Lower Bounds on the Multiparty Communication Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Power of Cooperation and Multihead Finite Systems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

1995

Optimal Lower Bounds on the Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

Sensing Versus Nonsensing Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994

A Note on the Density of Oracle Decreasing Time-Space Complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Conjunctive and Disjunctive Reducibilities to Sparse and Tally Sets Revisited.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1994

E-Complete Sets Do Not Have Optimal Polynomial Time Approximations.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

1991

Two Lower Bounds in Asynchronous Distributed Computation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

Semelectivity is not Sufficient.

[BibT_eX]

[DOI]

Imrich Vrto

Inf. Process. Lett., 1991

On the Power of Multiple Reads in a Chip.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

1989

On the Communication Complexity of Planarity.

[BibT_eX]

[DOI]

Pavel Pudlák

Proceedings of the Fundamentals of Computation Theory, 1989

1987

Zerotesting bounded one-way multicounter machines.

[BibT_eX]

[DOI]

Kybernetika, 1987

A Minimum-Area Circuit for l-Selection.

[BibT_eX]

[DOI]

Algorithmica, 1987

Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1985

Tight Chip Area Lower Bounds for Discrete Fourier and Walsh-Hadamard Transformations.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

1984

Two Nonlinear Lower Bounds for On-Line Computations

[BibT_eX]

[DOI]

Inf. Control., 1984

Lower Bounds on Communication Complexity

[BibT_eX]

[DOI]

Georg Schnitger

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

One-Way Simple Multihead Finite Automata are not Closed Under Concatenation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1983

Two Nonlinear Lower Bounds

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store

[BibT_eX]

[DOI]

Inf. Control., September, 1982

Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

Two Tapes are Better than One for Nondeterministic Machines

[BibT_eX]

[DOI]

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Multihead Finite State Automata and Concatenation.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1982

On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1982

1981

Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

A Time-Space Tradeoff for Language Recognition

[BibT_eX]

[DOI]