Bounded query machines: On NP and PSPACE

It is shown that NP is equal to PSPACE if and only if for every oracle set A, NP(A) is equal to the class NPQUERY(A) of languages accepted by nondeterministic polynomial space-bounded oracle machines that are allowed to query the oracle for A only a polynomial number of times. Further, it is shown that there is an oracle set B such that NPQUERY(B) is not equal to the class PQUERY(B) of languages accepted by deterministic polynomial space-bounded oracle machines that are allowed to query the oracle for B only a polynomial number of times.     

Qualitative relativizations of complexity classes

The principal result of this paper is a “positive relativization” of the open question “P = ?$\text{NP ? co-NP}$.” That is, the nondeterministic polynomial time-bounded oracle Turing machine endowed with designated accepting states and with designated rejecting states is considered, and suitable restrictions R of this device are developed such that $\text{P = NP ? co-NP}$ if and only if for every oracle D, P(D) = NP_R(D), where NP_R(D) is the class of languages L?NP(D) that are accepted by oracle machines operating with restrictions R. Positive relativizations are obtained for the P = ? $\text{U}$ ? co - $\text{U}$ and $\text{U}$ = ? NP questions also, where $\text{U}$ is the class of languages L in NP accepted by nondeterministic machines that operate in polynomial time and that have for each input at most one accepting computation. The restrictions developed here are “qualitative” in the sense that they restrict the form and pattern of access to the oracle. In contrast, a previous paper [3] developed quantitative relativizations-the number of distinct queries to the oracle is restricted-but no quantitative positive relativization of $\text{P = ? NP ? co-NP}$ is known.     

On relativizing auxiliary pushdown machines

We consider relativizing the constructions of Cook in [4] characterizing space-bounded auxiliary pushdown automata in terms of timebounded computers. LetS(n) ≥ logn be a measurable space bound. LetDT ^A[NT^A] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [nondeterministic] oracle Turing machine acceptor that runs in time 2 ^cS(n) for some constantc. LetDB _i ^A [NB _i ^A ] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [non-deterministic] oracle Turing machine acceptor with auxiliary pushdown that runs in spaceS(n) and never queries the oracle about strings longer than:S(n) ifi = 1, 2 ^cS(n) for some constantc, ifi = 2, + ∞ ifi = 3. Then we prove the following results: These contrast with Cook's (unrelativized) result:DT = NB = DB.     

On counting problems and the polynomial-time hierarchy

We consider the relation between the relativized polynomial time hierarchy and relativizations of Gill's class PP of sets recognizable in polynomial time by probabilistic Turing machines and of Valiant's class D≠P of sets polynomial time Turing reducible to functions that give the number of accepting computations of nondeterministic polynomial-time bounded Turing machines. The main result is that there exists an oracle set A such that PP^A ?(Π₂^P,A ∪ σ₂^P,A) ≠ ?, with the corollary that also D ≠P^A ? (Π₂^P,A ∪ σ₂^P,A ≠ ?. The proof is an application of Baker and Selman's technique for showing that σ₂^P,A ? σ₃^P,A for some oracle set A.     

On LR(k) grammars and languages

Many different definitions for LR(k) grammars exist in the literature. One of these definitions is chosen and many important implications are drawn from it. In particular, the LR(k) characterization theorem provides valuable information about chains of derivations. The LR(0) languages are then characterized by acceptance by deterministic pushdown automata with a special termination condition, by a condition on the strings in the language, and set theoretically. Important closure properties of the LR(0) languages and a related class of languages are then examined. These are used to examine some decidability questions relating to the class of LR languages. One of these questions is shown to be equivalent to the equality problem for deterministic pushdown automata.A survey of other LR(k) definitions is given and the exact differences are characterized. On the basis of this analysis, justification for the choice of definition used here is provided.     

Learning regular languages using RFSAs

Residual languages are important and natural components of regular languages and several grammatical inference algorithms naturally rely on this notion. In order to identify a given target language L, classical inference algorithms try to identify words which define identical residual languages of L. Here, we study whether it could be interesting to perform a tighter analysis by identifying inclusion relations between the residual languages of L. We consider the class of Residual Finite State Automata (RFSAs). An RFSA A is a NonDeterministic Automaton whose states corresponds to residual languages of the language L_A it recognizes. The inclusion relations between residual languages of L_A can be naturally materialized on A. We prove that the class of RFSAs is not polynomially characterizable. We lead some experiments which show that when a regular language is randomly drawn by using a nondeterministic representation, the number of inclusion relations between its residual languages is very important. Moreover, its minimal RFSA representation is much smaller than its minimal DFA representation. Finally, we design a new learning algorithm, DeLeTe2, based on the search for the inclusion relations between the residual languages of the target language. We give sufficient conditions for the identifiability of the target language. We experimentally compare the performance of DeLeTe2 to those of classical inference algorithms.     

Expressing uniformity via oracles

We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper:A-uniform circuits of logarithmic depth are of the same computational power asDLOGTIME-uniform circuits of logarithmic depth with oracle access to tally sets inA. This characterization does not only apply to classesA such as logarithmic space or polynomial time, but to all in some sense “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages. The first two authors were partially supported by DFG-La 618/1-1 and the third author was supported by DFG-SFB 0342 “KLARA.”     

A recursive and a grammatical characterization of the exponential-time languages

We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods. (i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class $\text{E}$², by means of subtitution and limited recursion of the form f(x, y + 1) = h(x, y), f(x, y), f(x, l(x, y))), l(x, y) ? y. (ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.     

Bounded DOL languages

For an alphabet A and a morphism h : A¹ → A¹, the set of words w such that the DOL language L(A, h, w) is a BOUNDED language is shown to be B¹, where B is an effectively computable subset of A. Consequently, BOUNDEDNESS is decidable for DOL languages. The result depends on the authors' recent results on periodic DOL languages. Interpretation of the result for polynomially bounded DOL languages is also considered.     

Extended macro grammars and stack controlled machines

K-extended basic macro grammars are introduced, where K is any class of languages. The class B(K) of languages generated by such grammars is investigated, together with the class LB(K) of languages generated by the corresponding linear basic grammars. For any full semi-AFL K, B(K) is a full AFL closed under iterated LB(K)-substitution, but not necessarily under substitution. For any machine type D, the stack controlled machine type corresponding to D is introduced, denoted S(D), and the checking-stack controlled machine type CS(D). The data structure of this machine is a stack which controls a pushdown of data structures from D. If D accepts K, then S(D) accepts B(K) and CS(D) accepts LB(K). Thus the classes B(K) are characterized by stack controlled machines and the classes LB(K), i.e., the full hyper-AFLs, by checking-stack controlled machines. A full basic-AFL is a full AFL K such that B(K) ? K. Every full basic-AFL is a full hyper-AFL, but not vice versa. The class of OI macro languages (i.e., indexed languages, i.e., nested stack automaton languages) is a full basic-AFL, properly containing the smallest full basic-AFL. The latter is generated by the ultrabasic macro grammars and accepted by the nested stack automata with bounded depth of nesting (and properly contains the stack languages, the ETOL languages, i.e., the smallest full hyper-AFL, and the basic macro languages). The full basic-AFLs are characterized by bounded nested stack controlled machines.     

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(logn) bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with n vertices and treewidth k. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in O(k ³log³ k) time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.     

UP and the low and high hierarchies: A relativized separation

The low and high hierarchies within NP were introduced by Schöning in order to classify sets in NP. It is not known whether the low and high hierarchies include all sets in NP. In this paper, using the circuit lower-bound techniques of Håstad and Ko, we construct an oracle set relative to which UP contains a language that is not in any level of the low hierarchy and such that no language in UP is in any level of the high hierarchy. Thus, in order to prove that UP contains languages that are in the high hierarchy or that UP is contained in the low hierarchy, it is necessary to use nonrelativizable proof techniques. Since it is known that UP^A is low for PP^A for all setsA, our result also shows that the interaction between UP and PP is crucial for the lowness of UP for PP; changing the base class to any level of the polynomial-time hierarchy destroys the lowness of UP.     

The level set method for the two-sided max-plus eigenproblem

We consider the max-plus analogue of the eigenproblem for matrix pencils, A???x?=?λ???B???x. We show that the spectrum of (A,B) (i.e., the set of possible values of λ), which is a finite union of intervals, can be computed in pseudo-polynomial number of operations, by a (pseudo-polynomial) number of calls to an oracle that computes the value of a mean payoff game. The proof relies on the introduction of a spectral function, which we interpret in terms of the least Chebyshev distance between A???x and λ???B???x. The spectrum is obtained as the zero level set of this function.     

Generateurs algebriques et systemes de paires iterantes

The notion of rational transduction is a valuable tool to compare the structures of different languages, in particular context-free languages.The explanation of this is a powerful property of rational transductions with respect to certain iterative pairs [8] and systems of iterative pairs (we define this notion in this paper), in a context-free language. (Intuitively, systems of iterative pairs describe combinations of simultaneous iterative pairs in a context-free language.)This property is the so-called Transfer Theorem, whose terms are:Let A and B be two context-free languages and let T be a rational transduction such that T(B) = A. If A has a strict system of iterative pairs σ, then B has a strict system of iterative pairs σ′, of the same type than σ.(This theorem has been proved in [8] for iterative pairs and we prove it here for systems of iterative pairs.)This theorem means that any combination of certain iterative pairs in the image language by a rational transduction must appear, in a similar way, in the source language.The main result of this paper is obtained by using the previous Transfer Theorem. This result is a characterization of context-free generators i.e. generators of the rational cone or, equivalently [10], of the full-AFL of context-free languages.     

Relativizing small complexity classes and their theories

Existing definitions of the relativizations of NC ¹, L and NL do not preserve the inclusions \({{\bf NC}^1 \subseteq {\bf L}, {\bf NL}\subseteq {\bf AC}^1}\). We start by giving the first definitions that preserve them. Here for L and NL we define their relativizations using Wilson’s stack oracle model, but limit the height of the stack to a constant (instead of log(n)). We show that the collapse of any two classes in \({\{{\bf AC}^0 (m), {\bf TC}^0, {\bf NC}^1, {\bf L}, {\bf NL}\}}\) implies the collapse of their relativizations. Next we exhibit an oracle α that makes AC ^k (α) a proper hierarchy. This strengthens and clarifies the separations of the relativized theories in Takeuti (1995). The idea is that a circuit whose nested depth of oracle gates is bounded by k cannot compute correctly the (k + 1) compositions of every oracle function. Finally, we develop theories that characterize the relativizations of subclasses of P by modifying theories previously defined by the second two authors. A function is provably total in a theory iff it is in the corresponding relativized class, and hence, the oracle separations imply separations for the relativized theories.     

The copying power of one-state tree transducers

One-state deterministic top-down tree transducers (or, tree homomorphisms) cannot handle “prime copying,” i.e., their class of output (string) languages is not closed under the operation L → {$(w$)^f(n) ∥ w?L, f(n) ? 1}, where f is any integer function whose range contains numbers with arbitrarily large prime factors (such as a polynomial). The exact amount of nonclosure under these copying operations is established for several classes of input (tree) languages. These results are relevant to the extended definable (or, restricted parallel level) languages, to the syntax-directed translation of context-free languages, and to the tree transducer hierarchy.     

Reductions between disjoint NP-Pairs

Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A B, then all queries belong to C D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.     

On generalized language equations

A system of generalized language equations over an alphabet A is a set of n equations in n variables: X_i = G_i(X₁,..., X_n), i = 1,...,n, where the G_i are functions from [P(A^*)]ⁿ into P(A^*), i=1,..., n, P(A^*) denoting the set of all languages over A. Furthermore the G_i are expressible in terms of set-operations, concatenations, and stars which involve the variable X_i as well as certain mixed languages. In this note we investigate existence and uniqueness of solutions of a certain subclass of generalized language equations. Furthermore we show that a solution is regular if all fixed languages are regular.     

Generating Local Addresses and Communication Sets for Data-Parallel Programs

Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We demonstrate a storage scheme for an array A affinely aligned to a template that is distributed across p processors with a cyclic(k) distribution that does not waste any storage, and show that, under this storage scheme, the local memory access sequence of any processor for a computation involving the regular section A(ℓ:h:s) is characterized by a finite state machine of at most k states. We present fast algorithms for computing the essential information about these state machines, and we extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time.