All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 4 of 4

Showing per page

Factoring and testing primes in small space

Viliam Geffert, Dana Pardubská (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We discuss how much space is sufficient to decide whether a unary given number n is a prime. We show that O(log log n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log n) and also in accept–ASPACE(log log n). Moreover, if the given n is...

Finite models and finitely many variables

Anuj Dawar (1999)

Banach Center Publications

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

From Bi-ideals to Periodicity

Jānis Buls, Aivars Lorencs (2008)

RAIRO - Theoretical Informatics and Applications

The necessary and sufficient conditions are extracted for periodicity of bi-ideals. They cover infinitely and finitely generated bi-ideals.

Function operators spanning the arithmetical and the polynomial hierarchy

Armin Hemmerling (2010)

RAIRO - Theoretical Informatics and Applications

A modified version of the classical µ-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory....

Currently displaying 1 – 4 of 4

Page 1