The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 41 –
60 of
120
We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application,...
We discuss some known and introduce some new hierarchies and
reducibilities on regular languages, with the emphasis on the
quantifier-alternation and difference hierarchies of the
quasi-aperiodic languages. The non-collapse of these hierarchies and
decidability of some levels are established. Complete sets in the
levels of the hierarchies under the polylogtime and some
quantifier-free reducibilities are found. Some facts about the
corresponding degree structures are established. As an application,
we...
Ko [26] and Bruschi [11] independently showed that, in
some relativized world, PSPACE (in fact, ⊕P) contains a set
that is immune to the polynomial hierarchy (PH). In this paper, we
study and settle the question of relativized separations with
immunity for PH and the counting classes PP, , and ⊕P
in all possible pairwise combinations. Our main result is that there
is an oracle A relative to which contains a set that is immune BPP⊕P.
In particular, this set is immune to PHA and to ⊕PA. Strengthening...
In [6] it was shown that shuffle languages
are contained in one-way-NSPACE(log n) and in P.
In this paper we show that nondeterministic one-way logarithmic space
is in some sense the lower bound for accepting shuffle languages.
Namely, we show that there exists a shuffle language which is not
accepted by any deterministic one-way Turing machine with space bounded by
a sublinear function, and that there exists a shuffle language which is
not accepted with less than logarithmic space even if we allow...
We formulate recursive characterizations of the class of elementary functions and the class of functions computable in polynomial space that do not require any explicit bounded scheme. More specifically, we use functions where the input variables can occur in different kinds of positions ?normal and safe? in the vein of the Bellantoni and Cook's characterization of the polytime functions.
Under the assumption that the Polynomial-Time Hierarchy does not collapse
we show for a regular language L:
the unbalanced polynomial-time leaf language class determined by L
equals iff L is existentially but not
quantifierfree definable in FO[<, min, max, +1, −1].
Furthermore, no such
class lies properly between NP and co-1-NP or NP⊕co-NP.
The proofs rely on a result of Pin and Weil
characterizing
the automata of existentially first-order definable languages.
Currently displaying 41 –
60 of
120