Pavol Duris

49 papers A* 11A 4B 4Journal 28Unranked 2
YearRankTypeTitle / Venue / Authors
2020 B conf
Randomization in Non-Uniform Finite Automata.
MFCS
Pavol Duris, Rastislav Královic, Richard Královic, Dana Pardubská, Martin Pasen, Peter Rossmanith
2020 J jnl
Tight hierarchy of data-independent multi-head automata.
J. Comput. Syst. Sci.
Pavol Duris, Rastislav Královic, Dana Pardubská
2018 — conf
Determinism and Nondeterminism in Finite Automata with Advice.
Adventures Between Lower Bounds and Higher Altitudes
Pavol Duris, Rafael Korbas, Rastislav Královic, Richard Královic
2014 J jnl
Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable.
Inf. Process. Lett.
Pavol Duris, Marek Kosta
2012 J jnl
A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.
Electron. Colloquium Comput. Complex.
Pavol Duris
2011 J jnl
Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable.
Electron. Colloquium Comput. Complex.
Pavol Duris, Marek Kosta
2011 — conf
Flip-pushdown automata: nondeterministic ε-moves can be removed.
ITAT
Pavol Duris, Marek Kosta
2011 J jnl
On Computational Power of Partially Blind Automata.
Electron. Colloquium Comput. Complex.
Pavol Duris
2004 J jnl
Multiparty communication complexity and very hard functions.
Inf. Comput.
Pavol Duris
2004 J jnl
On multi-partition communication complexity.
Inf. Comput.
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2004 J jnl
On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata.
J. Comput. Syst. Sci.
Pavol Duris, Juraj Hromkovic, Katsushi Inoue
2003 J jnl
On the computational complexity of infinite words.
Theor. Comput. Sci.
Pavol Duris, Ján Manuch
2001 J jnl
On Multipartition Communication Complexity
Electron. Colloquium Comput. Complex.
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2001 A conf
On Multipartition Communication Complexity.
STACS
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2001 B conf
On the Computational Complexity of Infinite Words.
MFCS
Pavol Duris, Ján Manuch
2000 J jnl
A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition
Electron. Colloquium Comput. Complex.
Pavol Duris, Juraj Hromkovic, Katsushi Inoue
2000 A conf
A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition.
CCC
Pavol Duris, Juraj Hromkovic, Katsushi Inoue
1998 J jnl
Lower Bounds on the Multiparty Communication Complexity.
J. Comput. Syst. Sci.
Pavol Duris, José D. P. Rolim
1998 A* conf
Power of Cooperation and Multihead Finite Systems.
ICALP
Pavol Duris, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys
1997 A conf
Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.
STACS
Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger
1997 J jnl
On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations
Electron. Colloquium Comput. Complex.
Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger
1995 A conf
Optimal Lower Bounds on the Multiparty Communication Complexity.
STACS
Pavol Duris, José D. P. Rolim
1995 A* conf
Sensing Versus Nonsensing Automata.
ICALP
Pavol Duris, Zvi Galil
1994 J jnl
A Note on the Density of Oracle Decreasing Time-Space Complexity.
Theor. Comput. Sci.
Pavol Duris, José D. P. Rolim
1994 J jnl
Conjunctive and Disjunctive Reducibilities to Sparse and Tally Sets Revisited.
Int. J. Found. Comput. Sci.
Pavol Duris, José D. P. Rolim
1994 B conf
E-Complete Sets Do Not Have Optimal Polynomial Time Approximations.
MFCS
Pavol Duris, José D. P. Rolim
1993 J jnl
On the Power of Multiple Reads in a Chip
Inf. Comput.
Pavol Duris, Zvi Galil
1991 A* conf
On the Power of Multiple Reads in a Chip.
ICALP
Pavol Duris, Zvi Galil
1991 J jnl
Semelectivity is not Sufficient.
Inf. Process. Lett.
Pavol Duris, Imrich Vrto
1991 J jnl
Two Lower Bounds in Asynchronous Distributed Computation.
J. Comput. Syst. Sci.
Pavol Duris, Zvi Galil
1989 B conf
On the Communication Complexity of Planarity.
FCT
Pavol Duris, Pavel Pudlák
1987 J jnl
A Minimum-Area Circuit for l-Selection.
Algorithmica
Pavol Duris, Ondrej Sýkora, Clark D. Thompson, Imrich Vrto
1987 J jnl
Lower Bounds on Communication Complexity
Inf. Comput.
Pavol Duris, Zvi Galil, Georg Schnitger
1987 A* conf
Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)
FOCS
Pavol Duris, Zvi Galil
1987 J jnl
Zerotesting bounded one-way multicounter machines.
Kybernetika
Pavol Duris, Juraj Hromkovic
1985 J jnl
Tight Chip Area Lower Bounds for Discrete Fourier and Walsh-Hadamard Transformations.
Inf. Process. Lett.
Pavol Duris, Ondrej Sýkora, Imrich Vrto, Clark D. Thompson
1984 J jnl
A Time-Space Tradeoff for Language Recognition.
Math. Syst. Theory
Pavol Duris, Zvi Galil
1984 A* conf
Lower Bounds on Communication Complexity
STOC
Pavol Duris, Zvi Galil, Georg Schnitger
1984 J jnl
Two Nonlinear Lower Bounds for On-Line Computations
Inf. Control.
Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rüdiger Reischuk
1984 J jnl
Two Tapes are Better than One for Nondeterministic Machines.
SIAM J. Comput.
Pavol Duris, Zvi Galil
1983 J jnl
One-Way Simple Multihead Finite Automata are not Closed Under Concatenation.
Theor. Comput. Sci.
Pavol Duris, Juraj Hromkovic
1983 A* conf
Two Nonlinear Lower Bounds
STOC
Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rüdiger Reischuk
1982 J jnl
Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines.
Theor. Comput. Sci.
Pavol Duris, Zvi Galil
1982 A* conf
Multihead Finite State Automata and Concatenation.
ICALP
Pavol Duris, Juraj Hromkovic
1982 A* conf
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store.
ICALP
Pavol Duris, Zvi Galil
1982 J jnl
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store
Inf. Control.
Pavol Duris, Zvi Galil
1982 A* conf
Two Tapes are Better than One for Nondeterministic Machines
STOC
Pavol Duris, Zvi Galil
1981 A* conf
A Time-Space Tradeoff for Language Recognition
FOCS
Pavol Duris, Zvi Galil
1981 A* conf
Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)
STOC
Pavol Duris, Zvi Galil