All reports by Author Pavol Duris:

__
TR12-092
| 6th July 2012
__

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

__
TR11-107
| 22nd July 2011
__

Pavol Duris#### On Computational Power of Partially Blind Automata

__
TR11-034
| 20th January 2011
__

Pavol Duris, Marek Kosta#### Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable

__
TR01-066
| 28th September 2001
__

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger#### On Multipartition Communication Complexity

__
TR00-027
| 11th April 2000
__

Pavol Duris, Juraj Hromkovic, Katsushi Inoue#### A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

__
TR97-029
| 20th August 1997
__

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger#### On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

Pavol Duris

In this paper we deal with one-way multi-head data-independent finite automata. A $k$-head finite automaton $A$ is data-independent, if the position of every head $i$ after step $t$ in the computation on an input $w$ is a function that depends only on the length of the input $w$, on $i$ ... more >>>

Pavol Duris

In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. ... more >>>

Pavol Duris, Marek Kosta

We prove that any propagating E0L system cannot generate the language containing all words of the form w#w. This result, together with some known ones, enable us to conclude that the flip-pushdown automata with k pushdown reversals (i.e. the pushdown automata with the ability to flip its pushdown) and E0L ... more >>>

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Pavol Duris, Juraj Hromkovic, Katsushi Inoue

The investigation of the computational power of randomized computations

is one of the central tasks of current complexity and algorithm theory.

In this paper for the first time a "strong" separation between the power

of determinism, Las Vegas randomization, and nondeterminism for a compu-

ting model is proved. The computing ...
more >>>

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

The study of the computational power of randomized

computations is one of the central tasks of complexity theory. The

main goal of this paper is the comparison of the power of Las Vegas

computation and deterministic respectively nondeterministic

computation. We investigate the power of Las Vegas computation for ...
more >>>