The store language of an automaton is the set of store configurations (state and store contents, but not the input) that can appear as an intermediate step in an accepting computation. A one-way nondeterministic finite-visit Turing machine ( fvNTM ) is a Turing machine with a one-way read-only input tape, and a single worktape, where there is some number k such that in every accepting computation, each worktape cell is visited at most k times. We show that the store language of every fvNTM is a regular language. Furthermore, we show that the store language of every fvNTM augmented by reversal-bounded counters can be accepted by a machine with only reversal-bounded counters and no worktape. Several applications are given to problems in the areas of verification and fault tolerance, and to the study of right quotients. We also continue the investigation of the store languages of one-way and two-way machine models where we present some conditions under which their store languages are recursive or non-recursive.

A language C is a code relative to L if every word in L has a unique factorization into words of C; this is a generalization of a code. We extend this notion to d-decodability (respectively, finite-decodability) for $$d \ge 1$$ , which means that every word in L has at most d (respectively, a finite number of) factorizations into words of C. We study decidability of testing this property on languages accepted (respectively, generated) by different machine (respectively, grammar) models. Then, we study applications of finite decodability towards a new notion regarding bounded languages called C-boundedness for a language C, leading to several new and general decidability results. In particular, we show that in any family with a decidable finiteness problem that is effectively closed under homomorphism, inverse homomorphism, and intersection with regular languages, it is decidable, given a language L in the family and a set $$\varSigma ^{\le l}$$ of all strings of length at most l over $$\varSigma $$ , whether there exist words $$w_1, \ldots , w_n$$ in $$\varSigma ^{\le l}$$ such that $$L \subseteq w_1^* \cdots w_n^*$$ . This can be considered as a finite analog of the boundedness problem. This also implies that the letter-boundedness problem is always decidable in these families.

A new model of multicounter machines is introduced where testing the counter status of a counter is optional, rather than existing models where they are always either required (traditional multicounter machines) or no status can be checked (partially-blind multicounter machines). If, in every accepting computation, each counter has a bounded number of occurrences where its status is tested and verified to be zero, then the machine is called finite-testable . One-way nondeterministic finite-testable multicounter machines are shown to be equivalent to partially-blind multicounter machines. However, one-way deterministic finite-testable multicounter machines are strictly more powerful than deterministic partially-blind machines. Interestingly, one-way deterministic finite-testable multicounter machines are shown to have a decidable containment problem. This makes it the most general known model where this problem is decidable, making the class important in the areas of model checking and formal verification. We also study properties of their reachability sets.

The notions of stability, anti-stability, and error-correctability of a language that is modified by making contextual insertions in the words of the language were introduced in a previous paper by Bottoni et al. in 2011, where it was shown that these properties are decidable for regular languages. The authors proposed investigating the decidability of these properties for other classes of languages. Here, we derive necessary and sufficient conditions for a class of languages to have decidable stable, anti-stable, and error-correctable properties, and use these conditions to exhibit general classes of languages (strictly greater than the regular languages) for which the properties are decidable, and also simple classes (the first such classes) for which the properties are undecidable. We obtain identical results for the case when contextual deletions (instead of insertions) are made in the words of the language, and also with mixes of insertions and deletions . Our constructions also demonstrate that certain general problems involving nondeterministic generalized sequential machines ( GSM s) applied to languages accepted by deterministic machine models are decidable, which is surprising as the deterministic language families do not need to be closed under GSM mappings.

Abstract We consider a general class of decision problems concerning formal languages, called “(one-dimensional) unboundedness predicates”, for automata that feature reversal-bounded counters (RBCA). We show that each problem in this class reduces—non-deterministically in polynomial time—to the same problem for just finite automata. We also show an analogous reduction for automata that have access to both a pushdown stack and reversal-bounded counters (PRBCA). This allows us to answer several open questions: For example, we show that it is $$\textsf{coNP}$$ coNP -complete to decide whether a given (P)RBCA language L is bounded, meaning whether there exist words $$w_1,\ldots ,w_n$$ w 1 , … , w n with $$L\subseteq w_1^*\cdots w_n^*$$ L ⊆ w 1 ∗ ⋯ w n ∗ . For PRBCA, even decidability was open. Our methods also show that there is no language of a (P)RBCA of intermediate growth. This means, the number of words of each length grows either polynomially or exponentially. Part of our proof is likely of independent interest: We show that one can translate an RBCA into a machine with $$\mathbb {Z}$$ Z -counters in logarithmic space, while preserving the accepted language.

We generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and decidability of emptiness for VPDA languages) carry ove r to the generalized models, but other results (e.g., determinization and closure under complementation) do not carry over, in general. We define a model that combines the desirable features of a VPDA and reversal-bounded counters, called 2-phase VPCM, and show that the deterministic and nondeterministic versions are equivalent and that the family of languages they define is closed under Boolean operations and has decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. We also investigate the finite-ambiguity and finite-valuedness problems concerning these devices.

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh's theorem enables us to represent any semilinear set as a pushdown automaton (PDA). We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh's theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.

A stateless multicounter machine has m-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accep

An important trend in the development of intelligent tutoring systems (ITS) has been that of integrating characteristics proper of human tutoring into their performance, with the aim of providing the student with a more personalized and friendly environment for learning according to his traits and progress. These characteristics may give the student the sensation that there is "someone" behind the program who follows his learning development and cares about him as a human tutor would. One of the most important highlights of personal tutoring is that of recognizing the student's affective state and reacting accordingly by expressing the pedagogical movements in an affectively suitable way. In this paper, a proposal for an affective behavior model to be used in ITS is presented. The aim of this model is to provide students with a suitable response from a pedagogical and affective viewpoint.

The e-services paradigm promises to enable rich, flexible, and dynamic inter-operation of highly distributed, heterogeneous network-enabled services. Among the challenges, a fundamental question concerns the design and analysis of composite e-services. This paper proposes techniques towards automated design of composite e-services. We consider the Roman model which represents e-services as activity-based finite state automata. For a given set of existing e-services and a desired e-service, does there exist a "mediator" which delegates activities in the desired e-service to existing e-services? The question was raised in an early study by Berardi et. al. for a restricted subclass of delegators which does not take into consideration of future activities. In this paper, we define a more general class of delegators called "lookahead" delegators and we show that the hierarchy based on the amount of lookahead is strict. We, then, study the complexity of constructing such delegators. We prove that in the case of deterministic e-services, a k-lookahead delegator can be computed in time polynomial in the size of target and subcontractor e-services, and exponential in k and the number of subcontractor e-services. We also present Wozart, an automated mediator construction tool implemented to realize our approaches.

An important class of queries in moving object databases involves trajectories. We propose to divide trajectory predicates into topological and non-topological parts; extend the 9 intersection model of Egenhofer-Franzosa to a 3-step evaluation strategy for trajectory queries: a filter step, a refinement step, and a tracing step.The filter and refinement steps are similar to region searches. As in spatial databases, approximations of trajectories are typically used in evaluating trajectory queries. In earlier studies, minimum bounding boxes (mbrs) are used to approximate trajectory segments which allow index structures to be built, e.g., TB-trees and R*-trees. The use of mbrs hinders the efficiency since mbrs are very coarse approximations especially for trajectory segments. To overcome this problem, we propose a new type of approximations, "minimum bounding octagon prism" mbop. We extend R*-tree to a new index structure "Octagon-Prism tree" (OP-tree) for mbops of trajectory segments. We conducted experiments to evaluate efficiency of OP-trees in performing region searches and trajectory queries. The results show that OP-trees improve region searches significantly over synthetic trajectory data sets to TB-trees and R*-trees and can significantly reduce the evaluation cost of trajectory queries compared to TB-trees.

Database applications for moving objects pose new challenges in modeling, querying, and maintenance of objects whose locations are rapidly changing over time. Previous work on modeling and querying spatio-temporal databases and constraint databases focus primarily on snapshots of changing databases. In this paper we study query evaluation techniques for moving object databases where moving objects are being updated frequently. We consider a constraint database approach to moving objects and queries. We classify moving object queries into: and queries. We argue that while traditional constraint query evaluation techniques are suitable for past queries, new techniques are needed for continuing and future queries. Motivated by nearest-neighbor queries, we define a query language based on a single generalized function f mapping from objects to continuous functions from time to ℝ. Queries in this language may be past, continuing, or future. We show that if f maps to polynomials, queries can be evaluated efficiently using the plane sweeping technique from computational geometry. Consequently, many known distance based queries can be evaluated efficiently.

Efficient evaluation of spatial join is an important issue in spatial databases. The traditional evaluation strategy is to perform a join of "minimum bounding rectangles" (MBR) of the spatial objects (MBR-filter) and evaluate the actual join of the objects using the results of the join on approximations. Improvements to add additional filtering using more accurate approximations were also considered. In the present paper, we develop efficient algorithms for evaluating joins of "trapezoids" without using MBR'S. For the case where there are no intersecting non-horizontal boundaries of trapezoids in the same set, a spatial join of two sets of N trapezoids can be evaluated in O(N logb N+k) I/Os, where b is the page size and k the number of trapezoid intersections. For the general case without any assumptions, a join can be done in O((N+l+k) logb N) I/Os, where l is the total number of intersections of non-horizontal boundaries within the same set, and N, k, b are the same as above. The new algorithms can be used to evaluate spatial joins for polygons. One possibility is to decompose polygons into trapezoids and apply a trapezoid join algorithm. In particular, this approach is efficient for "I/O bounded polygons" (each of which can be retrieved in a constant number of I/Os). Given two sets of N "I/O bounded polygons, we show that in the case where there are no boundary intersections among polygons of the same set, the join of the two sets can be computed in O(N log/sub b/ N+k) I/Os, and in the case where there is no such assumption, the join takes O((N+l+k) log/sub b/ N) I/Os, where b is the page size, k the number of pairs of intersecting polygons, and l the number of boundary intersections within the same polygon set. Another possibility is to approximate objects by I/O bounded polygons (e.g., 5-corner convex polygons) which are finer than rectangles and use the new algorithms as a filter.

Constraint databases integrate database technology with constraint solving to deal with new applications such as spatial or geographical applications and those requiring arithmetic computations. Although the conceptual framework is elegant, issues related to efficient query evaluation and optimization techniques have not been sufficiently addressed. We study efficient evaluation of spatial join in linear constraint databases in terms of the I/O complexity. We develop an extension of the classical B/sup +/-trees, called interval B/sup +/-trees, and show that they can be used to efficiently evaluate the spatial join of relations with dense-order and linear constraints. Specifically, we develop a general algorithm for joining two sets of rectangles using interval B/sup +/-trees. We show that the algorithm has the worst case I/O complexity of O(bNlog/sub b/(N/b)+k), where N is the number of input rectangles and k the number of intersections. We show that the algorithm can be used in performing joins of relations with linear constraints. For relations with dense-order constraints where the spatial objects are not strictly rectangles, we extend the algorithm so that it can process the natural join of two N-tuple relations within O(bNlog/sub b/(N/b)+k) I/Os, where k is the number of intersections. It remains open if one can achieve the same upper bound in the linear case.

This paper investigates load balancing strategies for clustered Alexandria digital library (ADL) servers. The ADL system, which provides on-line information searching and browsing of spatially-referenced materials through the World Wide Web, involves intensive database I/O and heterogeneous CPU activities. Clustering servers can improve the scalability of the ADL system in response to a large number of simultaneous access requests. One difficulty addressed is that clustered workstation nodes may be non-uniform in terms of CPU and I/O speeds. An optimization scheme is proposed in this paper to dynamically monitor the resource availability, use a low-cost communication strategy for updating load information among nodes, and schedule requests based on both I/O and computation load indices. Since the accurate cost estimation for processing database-searching requests is difficult, a sampling and prediction scheme is used to identify the relative efficiency of nodes for satisfying I/O and CPU demands of these requests. A set of experiments using the ADL traces have been conducted to verify the effectiveness of the proposed strategies.

We develop a new technique based on counter machines to study the containment and equivalence of queries with linear constraints overintegers Z, natural numbers M, rational numbers Q and real numbers RWe show that the problems are decidable in double exponential time with an exponential time lower bound for conjunctive queries with linear constraints over Z and lV, decidable in double exponential time for constant-free conjunctive queries with linear constraints over Q and R. For the general classes of conjunctive queries with linear constraints over Q and R, the problems are decidable in double exponential space using reductions to the first-order theory of reals with addition.We also use the counter machine technique to show that for "connected" first-order queries with linear constraints over Z and lV, the containment and equivalence problems are decidable over "bounded-degree databases".

The authors study some decision questions concerning two-way counter machines and obtain the strongest decidable results to date concerning these machines. In particular, it is shown that the emptiness, containment, and equivalence (ECE for short) problems are decidable for two-way counter machines whose counter is reversal-bounded (i.e., the counter alternates between increasing and decreasing modes at most a fixed number of times). This result is used to give a simpler proof of a recent result which shows that the ECE problems for two-way reversal-bounded pushdown automata accepting bounded languages (i.e., subsets of $w_{1}^{*} \dotsc w_{k}^{*}$ for some nonnull words $w_{1}, \dotsc , w_{k}$) are decidable. Other applications concern decision questions about simple programs. Finally, it is shown that nondeterministic two-way reversal-bounded multicounter machines are effectively equivalent to finite automata on unary languages, and hence their ECE problems are decidable also.

Investigates the pin redistribution problem (PRP) for multi-chip modules. A novel transformation to the max-flow problem is introduced. This approach provides an efficient algorithm for finding a 2-layer solution, whenever one exists. A greedy heuristic to find a k-layer solution is described. The approach can find a minimum layer solution for two variants of the PRP; when each net can be routed on more than one layer, and when source and target terminals are drilled through all layers. Except for the heuristic procedure which takes O(km/sup 4/ log/sup 2/ m) time, the algorithms take O(/spl verbar/S/spl verbar/km/sup 2/) time, where S is the set of source terminals, m is the number of rows and columns in the grid, and k is the number of layers required. One can show that generalizations of the k-layer PRP are NP-complete problems.>

We show that articulation points and bridges of permutation graphs can be found in O(logn) time using O(n/logn) processors on an EREW PRAM. The algorithms are optimal with respect to the time-processor product.

The authors give an efficient parallel algorithm for the string edit problem. The model of computation is a one-way linear array of identical finite-state machines (nodes). The data movement in the array is one-way, from left to right. For inputs of length n, the array uses n nodes. The algorithm can produce the actual minimum-cost edit sequence in linear time. The previous parallel algorithm for this problem runs in O(n) time on a one-way two-dimensional array of finite-state machines using n/sup 2/ nodes. The best serial (RAM) algorithm for the problem takes O(n/sup 2//log n) time and space. Applications to other problems such as the longest common subsequence and approximate pattern matching are discussed.>

The relation between reversals and alternation is studied in two simple models of computation: the 2-counter machine with a one-way input tape whose counters make only one reversal (1-reversal 2CM) and the one-way pushdown automaton whose pushdown store makes only one reversal (1-reversal PDA). The following is shown: (a) alternating 1-reversal 2CM’s accept all recursively enumerable languages; (b) alternating 1-reversal PDA’s accept exactly the languages accepted by exponential time-bounded deterministic TM’s. The first improves on the known result that alternating 1-reversal 4CM’s accept all recursively enumerable languages. The second improves an earlier result that alternating PDA’s with no restrictions on reversals accept exactly the exponential-time languages.

The authors present parallel algorithms for recognizing and parsing context-free languages on the hypercube. This algorithm is both time-wise and space-wise optimal with respect to the usual sequential dynamic programming algorithm. Also, the number of nonoverlapping interprocessor data transmissions for the recognition phase is small. It is noted that this is desirable since communication cost in reality is a function of the number of transmissions as well as transmission length. The authors present another recognition algorithm that achieves the same time and space bounds but employs a dynamic loading balancing technique to increase processor utilization. The results of implementing these algorithms on a 64-node NCUBE/7 MIMD hypercube machine are also given. The experimental evidence indicates that, while both recognition algorithms exhibit acceptable speedups, using load balancing results in significantly better performance. The authors obtain parallel algorithms with the same time and space bounds as above for the polygon triangulation problem and the matrix product chain problem.>

Consideration is given to the problem of mapping systolic array algorithms into efficient algorithms for a fixed-size hypercube architecture. The authors describe in detail several optimal implementations of algorithms given for one-way one- and two-dimensional systolic arrays. Since interprocessor communication is many times slower than local computation in parallel computers built to date, the problem of efficient communication is specifically addressed for these mappings. In order to validate the technique experimentally, five systolic algorithms were mapped in various ways onto a 64-node NCUBE/7 MIMD hypercube machine. The algorithms are for the following problems: the shuffle scheduling problem, finite impulse response filtering, linear context-free language recognition, matrix multiplication, and computing the Boolean transitive closure. Experimental evidence indicates that good performance is obtained for the mappings.>

This paper considers the problem of how the size of a nondeterministic finite automaton (nfa) representing a regular language depends on the type of ambiguity of the nfa. Primarily, the relationship between the ambiguity and the size in five types of nfa’s with increasing degrees of nondeterminism is studied: DFA (deterministic), ${\operatorname{UNA}}$ (unambiguous), ${\operatorname{FNA}}$ (finitely ambiguous), ${\operatorname{PNA}}$ (polynomially ambiguous), and ${\operatorname{ENA}}$ (exponentially ambiguous) nfa’s. The goal is to show “separation” among these classes, where a class A is said to be “separated” from B (written ($A,B$)) if for infinitely many n, there are machines of type B with n states whose minimal equivalent type A machine has more than $p(n)$ states for any polynomial p. Two classes are “polynomially equivalent” (written $A = B$) if machines of type A can be converted to machines of type B with only a polynomial increase in the number of states, and vice versa. For a class X, let $X(b)$) denote the restricted class of machines of type X with the restriction that the language accepted is bounded. The first main result compares the bounded restrictions of the five classes mentioned above. Specifically, the following is shown: $({\operatorname{DFA}}(b),{\operatorname{UNA}}(b)),({\operatorname{UNA}}(b),{\operatorname{FNA}}(b)),{\operatorname{FNA}}(b) = {\operatorname{PNA}}(b)$ and ${\operatorname{PNA}}(b) = {\operatorname{ENA}}(b)$, providing a complete picture of how the type of ambiguity affects the size complexity for unary and bounded languages. For unbounded languages it is conjectured that each of the five types of nondeterminism is separate from its higher types. But a proof does not exist at this time for two of the separations, the other two carrying over directly from the unary case. Candidates are offered that may be useful in proving the (other two) conjectured separations, and also a weaker form of separation in one case is shown. The notion of “concurrent conciseness” introduced by Kintala and Wotschke is studied. A class C is said to be concurrently concise over two classes A and B if $(A,B)$ and $(B,C)$ can be proved using the same collection of witness languages. One of the main results of this paper shows that, for unrestricted inputs, PNA is concurrently concise over ${\operatorname{DFA}}$ and ${\operatorname{UNA}}$. This answers an open problem of Stearns and Hunt. The succinctness problem is also studied through (regularity preserving) closure properties, an approach initiated by Sakoda and Sipser, and some interesting contrasts between various classes of nfa’s are shown.

In this paper, a very simple model of parallel computation is considered, and the question of how restricting the flow of data to be one way compares with two-way flow is studied. It is shown that the one-way version is surprisingly very powerful in that it can solve problems that seemingly require two-way communication. Whether or not one-way communication is strictly weaker than two-way is an open problem, although the conjecture in this paper is in the positive. It is shown, however, that proving this conjecture is at least as hard as some well-known open problems in complexity theory.

An algorithm for convolving a k*k window of weighting coefficients with an n*n image matrix on a pyramid computer of O(n/sup 2/) processors in time O(logn+k/sup 2/), excluding the time to load the image matrix, is presented. If k= Omega ( square root log n), which is typical in practice, the algorithm has a processor-time product O(n/sup 2/ k/sup 2/) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two (0, 1)-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state.>

Systolic tree architectures are presented for data structures such as stacks, queues, dequeues, priority queues, and dictionary machines. The stack, queue, and dequeue have a unit response time and a unit pipeline interval. The priority queue also has a unit response time, but the pipeline interval is 2. The response time and pipeline interval for the dictionary machine are O(log n) and O(1), respectively, where n is the number of data elements currently residing in the tree. In each node of the tree, the mechanism for controlling the transmission and distribution of data is finite state. This feature makes the designs presented here suitable for VLSI. If there are n data elements in the data structure, the depth of the tree is O(log n).>

The authors study the via assignment problem when vias are allowed to appear rowwise as well as columnwise. Previously they proved that the problem belongs to the class of NP-hard problems and therefore it is unlikely that polynomial-time algorithms exist for solving the problem. Two heuristics (HEU1 and HEU2) to solve the problem were proposed. HEU1 splits the nets before any routing is done while HEU2 assigns the nets alternately to via rows and via columns. Here they modify HEU2 so that the side of the board to which the nets are assigned first for connection is selected according to a desired ratio of board width to height.>

There are two simple models of parallel language recognizes: one-way cellular array (OCA) and one-way iterative array (OIA). For inputs of length n, both arrays consist of n identical finite-state machines (cells). The communication between cells is one way, from left to right. The difference in the two models is in the manner in which the input is applied. For the OCA, the input is applied to the cells in parallel. For the OIA, the input is applied serially to the leftmost processor. An input string is accepted if the rightmost cell eventually enters an accepting state. We show that OCA’s accept exactly the same class of languages as OIA’s. It is relatively easy to show that OIA’s can simulate OCA’s. The difficult part is the converse, i.e., that OCA’s can simulate OIA’s. This is rather surprising, since in an OIA, every cell of the array has access to each symbol of the input string, whereas in an OCA, the ith cell can only access the first i symbols of the input. This result, when combined with known results concerning OIA’s, answers some open questions concerning the computational complexity of OCA’s. We also prove some new results concerning linear-time OCR’s and OIA’s. For example, we show: (1) linear-time OCA’s are equivalent to $2n$-time OIA’s (note that $2n$-time is optimal for OIA’s); (2) the concatenation of a linear-time OCA language with a real-time (i.e. n-time) OCA language is a linear-time OCA language; (3) every bounded language accepted by a one-way multihead nondeterministic pushdown automaton is a linear-time OCA language.

We give efficient simulations of systolic arrays by unit-cost random-access machines (RAM’s). For example, we show that a one-dimensional systolic array operating in linear time can be simulated by a RAM in $O({{n^2 } / {\log ^2 n}})$ time. For the case of a two-dimensional systolic array, the simulation time is $O({{n^3 } / {\log ^{{3 / 2}} n}})$.

We show that a one-way two-dimensional iterative array of finite-state machines (2-DIA) can recognize and parse strings of any context-free language in linear time. What makes this result interesting and rather surprising is the fact that each processor of the array holds only a fixed amount of information (independent of the size of the input) and communicates with its neighbors in only one direction. This makes for a simple VLSI implementation. Although it is known that recognition can be done on a 2-DIA, previous parsing algorithms require the processors to have unbounded memory, even when the communication is two-way. We also consider the problem of finding approximate patterns in strings, the string-to-string correction problem, and the longest common subsequence problem, and show that they can be solved in linear time on a 2-DIA.

Previous studies of the single-row routing problem have been restricted to the minimization of the total number of horizontal tracks needed for the realization of a given set of nets. Therefore, it has been assumed that enough space exists between adjacent nodes to allow for the wiring. Due to this assumption, realizations obtained with previously proposed algorithms may require a large number of vertical tracks between adjacent nodes. In this paper, we study the single-row routing problem when the number of vertical tracks available between adjacent nodes is bounded by a positive integer called the crossover bound. We give some results concerning crossovers and prove that, for any given positive integer K, an instance can be constructed such that the vertical track requirement between adjacent nodes cannot be less than K. We develop a fast algorithm for the case when the number of horizontal tracks available as well as the number of vertical tracks available between adjacent nodes have been preset. We compare the performance of our algorithm to the performance of an algorithm (proposed in [6]) which is fast and does not consider the vertical track constraint. Our experiments show that, in all cases, the realizations found by our algorithm have the same street capacities as those obtained by the algorithm proposed in [6]. However, unlike the realizations found with the algorithm proposed in [6], the ones found by our algorithm have smaller crossover bounds. The computing time of our algorithm is, in general, no worse than the computing time of the algorithm proposed in [6].

We look at a very simple model of parallel computation and study the question of how restricting the flow of data to be one-way compares with two-way flow. A one-way linear iterative array (1LIA) is a finite one-dimensional array of identical finite-state machines (cells) in which information is allowed to move only in one direction- from left to right. For inputs of length n, the array uses n cells which are initially set to the quiescent state. The serial input, which is applied to the leftmost cell, is accepted if the rightmost cell ever enters an accepting state. We give results which show that 1LIA's are surprisingly very powerful in that they can accept languages which seemingly require two-way communication.

We present a tool that is useful in the design and analysis of systolic systems. Specifically, we give characterizations of systolic arrays in terms of (single processor) sequential machines which are easier to program and to analyze. We give several examples to illustrate the utility of the design tool. In particular, we show how systolic designs for such problems as integer bitwise multiplication, dynamic programming, and language recognition can easily be derived using the characterizations. We also present some new results concerning the properties and computational power of systolic arrays which can be obtained using the characterizations.

We look at a simple, but general model, of a systolic system called a trellis automaton (TA). A TA is equivalent in computational power to a one-dimensional unbounded cellular automaton (CA), a model of parallel computation which has been studied extensively in the literature. Different varieties of TA’s are equivalent to corresponding variations of CA’s. We present, for the first time, sequential machine characterizations of TA’s (CA’s). The sequential machines are useful and powerful tools for investigating properties of TA’s (CA’s). They ar easy to program because, unlike the parallel models, one does not have to deal with the problem of synchronization. Several applications are given. In particular, we prove a new speed-up theorem which is stronger than what has previously been shown.

We offer a methodology for simplifying the design and analysis of systolic systems. Specifically, we give characterization of systolic arrays in terms of (single processor) sequential machines which are easier to analyze and to program. We give several examples to illustrate the design methodology. In particular, we show how systolic arrays can be easily designed to implement priority queues, integer bitwise multiplication, dynamic programming, etc. Because the designs are based on the sequential machine, the constructions we obtain are much simpler then those that have appeared in the literature. We also give some results concerning the properties and computational power (e.g., speed-up, hierarchy, etc.) of systolic arrays.

The sunphficaUon and equivalence problems are examined for several classes of straightline programs.It is shown that the problems are unsolvable for all nontrivlal classes.For example, it is proved that there is no algorithm to determine if an arbRrary program using only the constructs x ,,--1, r ,-x + y, x ,,--x/y, where x/y ~s integer diwsion with truncation, computes the ftinction which has value l for all integer inputs.The result holds even if one considers only programs with three input variables which compute total 0/l-functions.Thus, under any criteria of smaplification, no algorithm exists for simphfymg such programs When x ,--x + y is replaced by x ~--x -y, the number of input variables can be reduced to two This ~s the best possible, since equivalence Is decidable for {x ~-1, x ~ x + y, x ,,-x --y, x ~ x *y, x ~--x/y}-programs wtth one input variable All the results translate directly to simdar results concermng arithmetic expressions.

Let Q be any algebraic structure and ~the set of all total programs over Q using the instruction set {z ,,--1, z ,,-x + y, z ,,--x -y, z ~ x * y, z ~--x/y}.(A program is total if no division by zero occurs during any computation ) Let the equivalence problem for ~ be the problem of deciding for two given programs in ~whether or not they compute the same funcuon The following results are proved:(1) If Q is an inftmte field (e.g, the rauonal numbers or the complex numbers), then the equwalence problem for ~ is probabilistlcally decidable in polynomml time.The result also holds for programs with no dwlslon instructions and Q an infimte integral domain (e.g., the integers).(2) If Q is a finite field, or if Q is a fimte set of integers of cardmahty _>2, then the equivalence problem is NP-hard.The case when the field Q is finite but its cardinality is a funcuon of the size of the instance to the eqmvalence problem is also considered An example is shown for which a sharp boundary between the classes NP-hard and probabihsticaUy decidable exists (provided they are not identical classes).

We study the space and time complexity of functions computable by simple loop-free programs operating on integers. In particular, we show that any function $f(x_1 , \cdots ,x_k )$ computable by a program using only comparison-based conditional forward branching instructions and the arithmetic operations $ + , - $, and truncating division by integer constants (such programs compute exactly the functions definable in Presburger arithmetic) can be computed by an off-line Turing machine in space $s(n)$ and time $n^2 /s(n)$ for any reasonable space bound $s(n)$ between $\log n$ and n. Moreover, the space-time trade-off is optimal.

Fast simulations of time-bounded single-tape TM’s and offline TM’s (i.e., TM’s with a two-way read-only input and one storage tape) by space-bounded TM’s of the same type are presented. The following results are shown: (1) Any language accepted by a single-tape TM in time $T(n) \geqq n^2 $ can be accepted by a single-tape TM in space $T^{1/2} (n)$ and time $T^2 (n)$. (2) Any language accepted by an offline TM in time $T(n) \geqq n $ can be accepted by an offline TM in space $(T(n)\log n)^{1/2} $ and time $T^{3/2} (n)(T^{1/2} (n) + n/(\log n)^{1/2} )$. Similar (in fact, in some sense, stronger) results hold for nondeterministic TM’s. For example: (3) Any language accepted by a single-tape nondeterministic TM in time $T(n) \geqq n^2 $ can be accepted by a single-tape nondeterministic TM in space $S(n)$ and time $T^2 (n)/S(n)$ for any $T^{1/2} (n) \leqq S(n) \leqq T(n)$. Similar time-space tradeoffs hold for TM’s with a multidimensional storage tape. Previously known results on simulation of time bounded by space bounded TM’s had exponential (in $T(n)$) time complexity.

Let Q be the class of determmistlc two-way l-counter machines accepting only bounded languages Each machine m Q has the property that m every accepting computation, the counter makes at most a fixed number of reversals It is shown that the emptiness problem for Q is decidable.When the counter is unrestricted or the machine is prowded with two reversal-bounded counters, the emptiness problem becomes undecidable.The decidability of the emptmess problem for Q is useful in proving the solvabdity of some number-theoreuc problems It can also be used to prove that the language L = {u~u21 ~ >-0} cannot be accepted by any machme in Q (u~ and u2 are &stmct symbols).The proof techmque ~s new m that it does not employ the usual "pumpmg," "counting," or "thagonal" argument.Note that L can be accepted by a deterministic two-way machine with two counters, each of which makes exactly one reversal Categories and Subject Descriptors.F. 1.1 IComputation by Abstract Devicesl: Modds of

Let $\mathbb{C}$ be the set of all straight-line programs with one input variable, x, using the following instruction set: $y \leftarrow 0$, $y \leftarrow 1$, $y \leftarrow y + w$, $y \leftarrow y - w$, $y \leftarrow y * w$, and $y \leftarrow \lfloor y/w \rfloor $. We show that two programs in $\mathbb{C}$ are equivalent over integer inputs if and only if they are equivalent on all inputs x such that $|x| \leqq 2^{2^{\lambda r^2 } } $ ($\lambda $ is a fixed positive constant and r is the maximum of the lengths of the programs). In contrast, we prove that the zero-equivalence problem (deciding whether a program outputs 0 for all inputs) is undecidable for programs with two input variables. An interesting corollary is the following: Let $\mathbb{N}$ be the set of natural numbers and f be any total one-to-one function from $\mathbb{N}$ onto $\mathbb{N} \times \mathbb{N}$ (f is called a pair generator. Such functions are useful in recursive function theory and computability theory.) Then f cannot be computed by any program in $\mathbb{C}$.

We consider a simple class of loop-free programs whose instruction repertoire consists of $x \leftarrow 0$, $x \leftarrow c$, $x \leftarrow cx$, $x \leftarrow x/c$, $x \leftarrow x + y$, $x \leftarrow x - y$, $\textbf{skip } l$, $\textbf{if } p(x,y)$$\textbf{then skip }l$, and $\textbf{halt}$. (x and y are integer variables, c is a positive integer, $x/c$ is integer division, l is a nonnegative integer, and $p(x,y)$ is a predicate of the form $x > y$, $x \geqq y$, $x = y$, $x \ne y$, $x \leqq y$, or $x < y$; $\textbf{skip }l$ causes the $(l + 1)$st instruction following the current instruction to be executed next.) We show that the equivalence problem for this class is decidable in $2^{\lambda N^2 } $ time ($N = $ sum of the sizes of the programs and $\lambda $ is a fixed positive constant). The bound cannot be reduced to a polynomial in N unless ${\text{P}} = {\text{NP}}$. In fact, we have the following rather surprising result: The equivalence problem for programs with one input variable (which also serves as the output variable) and one auxiliary variable using only instructions $x \leftarrow 2x$, $x\leftarrow x/2$, and $x \leftarrow x + y$ is NP-hard.

Let Q be the class of deterministic two-way one-counter machines accepting only bounded languages. Each machine in Q has the property that in every accepting computation, the counter makes at most a fixed number of reversals. We show that the emptiness problem for Q is decidable. When the counter is unrestricted or when the machine is provided with two reversal-bounded counters, the emptiness problem becomes undecidable. The decidability of the emptiness problem for Q is useful in proving the solvability of some numbertheoretic problems. It can also be used to prove that the language L = {u1iu2i2|i≥0} cannot be accepted by any machine in Q (u1 and u2 are distinct symbols). The proof technique is new in that it does not employ the usual "pumping", "counting", or "diagonal" argument. Note that L can be accepted by a deterministic two-way machine with two counters, each of which makes exactly one reversal.

The complexity of the eqmvalence problem for several sunple programming languages ,s investigated.In pamcular, ~t is shown that a class of programs, called XL, has an NP-complete mequwalence problem; hence its equivalence problem is decidable in determimstw tune 2 p~N~, wherep(N) ,s a polynomtal in the sum of the stzes of the programs.This bound is a four-level exponential improvement over a previously known result A very sunple subset of XL, called SL, is also considered, and it is shown that every XL-program ~s polynomial-time reducible to an eqmvalent SL-program.Moreover, SL is minimal in the sense that all its mstrucUons are independent On the other hand, XL Is maximal m that a "slight" generalization yields a language with an undecidable eqmvalence problem.XL-programs realize precisely the relations (functions) definable by Presburger formulas.

Let $\mathcal{F}$ be the smallest class of functions on the natural numbers containing the functions $U_i^n (x_1 , \cdots ,x_n ) = x_i $, $S(x) = x + 1$, $A(x,y) = x + y$, $D(x,y) = x \dot{-} y$, $C(x,y) = (1 \dot{-} y)x$, $T_k (x) = \lfloor x/k \rfloor $ and losed under composition. It is shown that $\mathcal{F}$ is exactly the class of functions definable by Presburger formulas. Moreover, for Presburger functions with finite output range, $A(x,y)$ and $C(x,y)$ can be deleted from the list of initial functions. Characterizations of $\mathcal{F}$ and its subclasses in terms of simple programs are also given. An example is the following: A function is in $\mathcal{F}$ if and only if it is computable by a program which contains only instructions of the form $x \leftarrow x + 1$, $x \leftarrow x \dot{-} 1$, $x \leftarrow y$, and $\textbf{do } x \cdots \textbf{ end}$, where $\textbf{do}$’s cannot be nested.

We look at several classes of straight-line programs and show that the equivalence problem is either undecidable or computationally intractable for all but the trivial classes. For example, there is no algorithm to determine if an arbitrary program (with positive, negative, or zero integer inputs) using only constructs x ← 1, x ← x + y, x ← x/y (integer division) outputs 0 for all inputs. The result holds even if we consider only programs which compute total 0/1 - functions. For programs using constructs x ← 0, x ← c, x ← cx, x ← x/c, x ← x + y, x ← x − y, skip l, if p(x) then skip l, and halt,1 the equivalence problem is decidable in [equation] time (λ is a fixed positive constant and N is the maximum of the sizes of the programs). The bound cannot be reduced to a polynomial in N unless P = NP. In fact, we prove the following rather surprising result: The equivalence problem for programs with one input/output variable and one intermediate variable using only constructs x ← x + y and x ← x/2 is NP-hard. We also show the decidability of the equivalence problem for a certain class of programs and use this result to prove the following: Let IN be the set of natural numbers and f be any total one-to-one function from IN onto IN × IN. (f is called a pair generator. Such functions are useful in recursive function and computability theory.) Then f cannot be computed by any program using only constructs x ← 0, x ← c, x ← x + y, x ← x − y, x ← x * y, x ← x/y, skip l, if p(x) then skip l, and halt.

We investigate the use of path systems in automata theory and computational complexity. A new framework is developed which brings together the main constructions of path systems corresponding to machine models as well as the main algorithms for solving such path systems. Applications to resource-bounded computation are given.

It is shown that the class of relations (functions) definable by Presburger formulas is exactly the class of relations (functions) computable by finite-reversal multicounter machines.

Systems of nonlinear equations of the form D Aft = ~(x), where A is an m × n matrix of ratmnal constants and fi = (yl, , y.), 8(x) = (ol(x), , on(x)) are column vectors, are considered Each o,(x) is of the form r,(x) or lr,(x)], where r,(x) is a rational function ofx with raUonal coefficients It Is shown that the problem of determining for a given system D whether there exists a nonnegatlve integral solution (yh,, y., x) satisfying Dts deodable In fact, the problem is NP-complete when restricted to systems D m which the maximum degree of the polynomials defining the o,(x)'s is bounded by some fixed polynomial m the length of the representation of D Some recent results connecting Dmphantme equations and counter machines are briefly mentioned.KEY WORDS AND PHRASES Hdbert's tenth problem, nonhnear integer programming, Dlophantme equation, decldabthty, NP-complete, polynomial time-bounded Turmg machine, counter machine CR CATEGORIES 5 23, 5 25, 5 26, 5 27, 5 41 lntroducttonHilbert's tenth problem [7] is the problem of determining for a given polynomial p(xl ..... xn) (or a system of polynomials p,(xl .... xn), 1 _< i _< m) with integer coefficients whether it has a nonnegatlve integer solution, i.e., nonnegatlve integers cq, ..., an such that p(al ..... an) = 0 (p,(a~ ..... an) = 0 for 1 _< t _< m).Hilbert's tenth problem is undecidable for (i) (iI) polynomials of degree 4 [14, 18], polynomials in t3 unknowns [15] (it was reported m [13] that this has been reduced to 9 unknowns), and (iii) systems of quadratic polynomials [3,9].On the other hand, Hilbert's tenth problem is decidable for (iv) polynomials in 1 unknown and (v) polynomials of degree 2 [17].It is not known whether the degree 4 in (i) and the 9 unknowns in (ii) are minimal.Also, the minimal number of quadratic polynomials needed to prove the undecidability in (iii) is not known.A decision procedure for a large class of polynomials in 2 unknowns is known [3] but not yet for the general case.For 3 unknowns almost nothing is known.Pinpointing the precise boundary between decidability and undecidability of Hilbert's tenth problem with respect to the degree, the number of unknowns, and number of quadratic polynomials in the system remains an interesting research problem.A related problem which is of practical interest is that of finding special classes of polynommls (or systems of polynomials) for which Hilbert's tenth problem is decidable This paper studies one such class.Consider a system of nonhnear equations of the form D: Aft = ~(x), where A is an m X n matrix of rational constants and fi = (yl ..... yn), ~(x) = (ol(x) ..... o,~(x)) are column

@, where ri(x) is a rational function of x with rational coefficients. It is shown that the problem of determining for a given system D whether there exists a nonnegative integral solution (y1,...,yn,X) satisfying D is decidable. In fact, the problem is NP-complete when restricted to systems D in which the maximum degree of the polynomials defining the σi(x)'s is bounded by some fixed polynomial in the length of the representation of D. Some recent results connecting Diophantine equations and counter machines are briefly mentioned.

Decidable and undecldable properties of various classes of two-way multlcounter machines (deterministic, nondetermmlstlc, multttape, pushdown store augmented) with reversal-bounded input and/or counters are investigated In particular It IS shown that the emptiness, infiniteness, dlsjointness, containment, universe, and equivalence problems are decidable for the class of deterministic two-way multlcounter machines whose input and counters are reversal-bounded

It is shown that the equivalence problem is unsolvable for $\varepsilon $-free nondeterministic generalized sequential machines whose input/output are restricted to unary/binary (binary/unary) alphabets. This strengthens a known result of Griffiths. Applications to some decision problems concerning right-linear grammars and directed graphs are also given.

It is shown that the equivalence problem is unsolvable for ε-free nondeterministic generalized sequential machines whose input/output are restricted to unary/binary (binary/unary) alphabets. This strengthens a known result of Griffiths. Applications to some decision problems concerning right-linear grammars and directed graphs are also given.

The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n .

We study the performance of LPT (largest processing time) schedules with respect to optimal schedules in a nonpreemptive multiprocessor environment. The processors are assumed to have different speeds and the tasks being scheduled are independent.

We look at a restricted model of a multihead pushdown automaton and use some of its properties to show the existence of algorithms for some decision problems concerning code sets and vector addition systems.

Given a positive integer M and n pairs of positive integers (p~, cD, , (p. , c.), maximize the sum~ ~p~ subject to the constramts~ ~c, < M and ~, = 0 or 1 This is the well-known 0/1 knapsack problem An algorithm is presented which finds for any 0 < e < 1 an approximate solution P satisfying (P* -P)/P* < ~, where P* is the desired optimal sum Moreover, for any fixed e, the algorithm has time complexity 0(n log n) and space complexity O(n) Modification of the algorithm for the unbounded knapsack problem where the ~,'s can be any nonnegative integer results in a O(n) computing time A hnear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that p,/c, is the same for all 1 < z < n KEY WORDS AND PHRASES.knapsack problem, sum of subset problem, P-complete problem, polynomial time algorithm, approximation algorithm CR CATEGORIES. 5 25, 5.39, 5 42

We look at several variations of the single fault detection problem for combinational logic circuits and show that deciding whether single faults are detectable by input-output (I/O) experiments is polynomially complete, i.e., there is a polynomial time algorithm to decide if these single faults are detectable if and only if there is a polynomial time algorithm for problems such as the traveling salesman problem, knapsack problem, etc.

The effect of increasing the size of the worktape alphabet of Turing machines with a read-only input and a single worktape operating within space $L(n) = n^r $ is investigated. In particular, it is shown that nondeterministic such machines with $m + 1$ worktape symbols are more powerful than those with m symbols.

A set of sufficient conditions on tape functions Ll(n) and L2(n) is presented that guarantees the existence of a set accepted by an Ll(n)-tape bounded nondeterministic Turing machine, but not accepted by any L~(n)-tape bounded nondeterministic Turing machine.Interesting corollaries arise.For example, it is shown that, for integers m >_ 0, p > 1, and q > 1, there is a set accepted by an [n~+(P/q)]-tape bounded nondeterministic Turing machine that is not accepted by any [nm+(p/(q+l))]-tape bounded nondeterministic Turing machine.

Finite-state sequential machine model - proof of equivalence and procedures for transforming one model to other preserving machine minimality