Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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.

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 >>>

TR11-107 | 22nd July 2011
Pavol Duris

On Computational Power of Partially Blind Automata

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 >>>

TR11-034 | 20th January 2011
Pavol Duris, Marek Kosta

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

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 >>>

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition Communication Complexity

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 >>>

TR00-027 | 11th April 2000
Pavol Duris, Juraj Hromkovic, Katsushi Inoue

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

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint