On efficient deterministic simulation of turing machine computations below logaspace

It is shown that a bounded language accepted by a nondeterministic Turing machine in spaceS(n o(logn) can be accepted by a deterministic Turing machine in space MAX {(s(nn))², logn}. This can be interpreted as extending Savitch's algorithm below logspace. Results of Alt can be used to show that in the general case the indicated space bound cannot be improved. The result can also be interpreted as a sharpening in the special case of bounded languages of the results of Monien and Sudborough.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

The complexity of ranking simple languages

Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1-way unambiguous auxiliary pushdown automata operating in polynomial time is inNC ⁽²⁾. We also prove negative results about ranking for several classes of simple languages.C is rankable in deterministic polynomial time iffP=P ^#P , whereC is any of the following six classes of languages: (1) languages accepted by logtime-bounded nondeterministic Turing machines, (2) languages accepted by (uniform) families of unbounded fan-in circuits of constant depth and polynomial size, (3) languages accepted by 2-way deterministic pushdown automata, (4) languages accepted by multihead deterministic finite automata, (5) languages accepted by 1-way nondeterministic logspace-bounded Turing machines, and (6) finitely ambiguous linear context-free languages.This research was partially supported by the National Science Foundation under Grant DCR-8696097. A preliminary version of this paper was presented at the 3rd Annual Structure in Complexity Theory Conference, Washington, DC, June 1988.     

Relations between diagonalization,proof systems,and complexity gaps

In this paper we study diagonal processes over time bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “clock” in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. These diagonalization methods also show that the Gap Theorem for resource bounded computations can hold only for those complexity classes which differ from the corresponding provable complexity classes. Furthermore, we show that there exist recursive time bounds T(n) such that the class of languages for which we can formally prove the existence of Turing machines which accept them in time T(n) differs from the class of languages accepted by Turing machines for which we can prove formally that they run in time T(n). We also investigate the corresponding problems for tape bound computations and discuss the difference time and tapebounded computations.     

Stack languages and log n space

We consider the space complexity of stack languages. The main result is: if a language is accepted by a deterministic (nondeterministic) one-way stack automaton then it is the image under a nonerasing homomorphism of a language accepted by a deterministic (nondeterministic) Turing machine that operates within space log n.     

Comparing Verboseness for Finite Automata and Turing Machines

A language is called (m,n)-verbose if there exists a Turing machine that enumerates for any n words at most m possibilities for their characteristic string. This notion is compared with (m,n)-fa-verboseness, where instead of a Turing machine a finite automaton is used. By use of a new diagonalisation method, where finite automata trick Turing machines, it is shown that all (m,n)-verbose languages are (h,k)-verbose iff all (m,n)-fa-verbose languages are (h,k)-fa-verbose. In other words, Turing machines and finite automata behave exactly the same way with respect to inclusion of verboseness classes. This identical behaviour implies that the nonspeedup theorem also holds for finite automata. As an application of the theoretical framework, a lower bound is derived on the number of bits that need to be communicated to finite automata protocol checkers for nonregular protocols.     

On alternation II

Summary Every deterministic t(n)-time bounded multitape Turing machine can be simulated by an alternating t(n) loglog t(n)/log t(n)-time bounded Turing machine.If the depth of every directed acyclic graph with n edges can be reduced to log n by removing only o(n) edges, then in linear time nondeterministic multitape Turing machines can recognize mor languages than deterministic multitape Turing machines. For some graphs reduction of the depth to log n requires the removal of (n/loglog n) edges. A graph theoretic condition is given, which implies that obliviousness reduces the power of multitape Turing machines.A preliminary version of this paper was presented at the GI-conference on Theoretical Computer Science 1979Part of this research was done while the author was visiting the Laboratoire de recherches en informatique de l'université de Paris sud under DAAD-grant 311-f-HSLA-soe     

Communicating processes,scheduling, and the complexity of nontermination

In this paper we study the computational complexity of the nontermination problem for systems of communicating processes with respect to five types of scheduling schemes, namely, round-robin, random, priority, first-come-first-served, and equifair schedules. We show that the problem is undecidable (₁-complete) with respect to round-robin, first-come-first-served, and priority scheduling; whereas it is decidable with respect to random and equifair scheduling. (Here ₁ denotes the set of languages whose complements are recursively enumerable.) For a restricted class of systems in which the communication channels between processes are of unit capacity, we show that the nontermination problem is solvable inO(k ² logn) nondeterministic space for round-robin, random, priority, and first-come-first-served scheduling, and inn ^{o(k 2}) nondeterministic time for equifair scheduling, wherek is the number of processes andn is the size of the maximal process. We are also able to establish a lower bound of ((k–59)/20*logn) nondeterministic space for all five types of scheduling schemes.     

One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.     

A Turing machine time hierarchy

The time separation results concerning classes of languages over a single-letter alphabet accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer and Meyer (1978), are supplemented. Moreover, via a universal machine a modified time complexity measure UTIME of Turing machines computations which is sensitive to multiplication by constants (i.e., UTIME(t) ? UTIME(kt), where UTIME(t) is the class of languages of complexity not larger than t) is introduced. On the level of this measure, the results concerning languages over one- and two-letter alphabets are refined. The proof tools are versions of a translational diagonalization and of an unpadding technique.     

Turing machines with access to history

We study remembering Turing machines, that is Turing machines with the capability to access freely the history of their computations. These devices can detect in one step via the oracle mechanism whether the storage tapes have exactly the same contents at the moment of inquiry as at some past moment in the computation. The s(n)-space-bounded remembering Turing machines are shown to be able to recognize exactly the languages in the time-complexity class determined by bounds exponential in s(n). This is proved for deterministic, non-deterministic, and alternating Turing machines.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

Towards separating nondeterminism from determinism

The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) ^1/k ). This implies, for example that for any positive integer,l,l k, there is a language accepted by an ^l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n ^l ) andO((logn) ^l ) respectively for anyl. Such a result is not provable by direct diagonalization because we do not have time to simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.Supported by NSF Grant No. MCS-8105557     

A note on three-dimensional finite automata

This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n²logn (n³) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n² (n²) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's.     

Unbounded-error quantum computation with small space bounds

We prove the following facts about the language recognition power of quantum Turing machines (QTMs) in the unbounded error setting: QTMs are strictly more powerful than probabilistic Turing machines for any common space bound s satisfying s(n)=o(loglogn). For “one-way” Turing machines, where the input tape head is not allowed to move left, the above result holds for s(n)=o(logn). We also give a characterization for the class of languages recognized with unbounded error by real-time quantum finite automata (QFAs) with restricted measurements. It turns out that these automata are equal in power to their probabilistic counterparts, and this fact does not change when the QFA model is augmented to allow general measurements and mixed states. Unlike the case with classical finite automata, when the QFA tape head is allowed to remain stationary in some steps, more languages become recognizable. We define and use a QTM model that generalizes the other variants introduced earlier in the study of quantum space complexity.     

Shuffle languages are in P

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.