Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with automata:
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 >>>

TR00-075 | 7th September 2000
Andreas Klein, Martin Kutrib

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

Deterministic k-tape and multitape Turing machines with one-way,
two-way and without a separated input tape are considered. We
investigate the classes of languages acceptable by such devices with
time bounds of the form n+r(n) where r in o(n) is a sublinear
function. It is shown that there ... more >>>

TR01-040 | 16th May 2001
Pierre Péladeau, Denis Thérien

On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... more >>>

TR05-152 | 9th December 2005
Oded Lachish, Ilan Newman

Languages that are Recognized by Simple Counter Automata are not necessarily Testable

Combinatorial property testing deals with the following relaxation of
decision problems: Given a fixed property and an input $f$, one wants
to decide whether $f$ satisfies the property or is `far' from satisfying
the property.
It has been shown that regular languages are testable,
and that there exist context free ... more >>>

TR12-069 | 23rd March 2012
Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

On the complexity of computing minimal unsatisfiable LTL formulas

We show that (1) the Minimal False QCNF search problem (MF-search) and
the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ... more >>>

ISSN 1433-8092 | Imprint