The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
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.
The necessary and sufficient conditions are extracted for periodicity of bi-ideals. They cover infinitely and finitely generated bi-ideals.
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