Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.     

Undirecteds-t connectivity in polynomial time and sublinear space

Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n ^1/2log₂ nsnlog₂ n, and timeO(((m+n)n ² log² n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO(n ^1/logn), for 2log₂ n, and timen ^O(). For constant the time remains polynomial.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

Gradually intractable problems and nondeterministic log-space lower bounds

The paper places five different problems (thek-pebble game problem, two problems aboutk finite automata, the reachability problem for Petri nets withk tokens, and the teachability problem for graphs whose k-dimensional edge sets are described by Cartesian products ofk factors) into the hierarchyNL _k of problems solvable by nondeterministic Turing machines ink-log₂ n space (and binary tape alphabet, to avoid tape speed-up). The results, when combined with the conjecture thatNL _i contains problems that requireO(n ^k ) deterministic time, show that these problems, while inP for every fixed value ofk, have polynomial deterministic time complexities with the degree of the polynomial growing linearly with the parameterk, and hence are, in this sense, gradually intractable.     

Sufficiency conditions for existence of an optimal feedback control in stochastic mechanics

In the framework of stochastic mechanics, the following problem is considered: in a set of admissible feedback controls v, with range inE ⁿ , find one minimizing the expectationE _sx { _s ^T L(t, (t), (t, (t)))dt + W _T ((T))} for all (s, x) [0,T) E ⁿ , whereL(t, x, ) = (/12)m ² – U(t, x) is the classical action integrand and is an-dimensional diffusion process in the weak sense, (see Bensoussan, 1982) with drift and diffusion coefficientD constant > 0.W _T andU are given real functions. Sufficiency conditions for the existence of such an optimal feedback control are given. Dedicated to George Leitmann Recommended by G.J. Olsder Presented at the Third Workshop on Control Mechanics in honor of George Leitmann, January 22–24, 1990, University of Southern California, Los Angeles, California (USA).     

Constructing sets of functions which have a givenF-cardinality

The termF-cardinality of (=F-card()) is introduced whereF: ^{n n} is a partial function and is a set of partial functionsf: ^{n n} . TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF: ^{n n} and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions.     

Nonpreemptive scheduling of periodic tasks in uni- and multiprocessor systems

In this paper we study the problem of scheduling a set of periodic tasks nonpreemptively in hard-real-time systems, where it is critical for all requests of the tasks to be processed in time. A taskT is characterized by itsarrival time A, itsperiod P, and itsexecution time C. Starting fromA, a new request ofT arrives in everyP units of time, requestingC units of processing time, and itsdeadline coincides with the arrival of the next request ofT. All requests must be processed nonpreemptively to meet their corresponding deadlines. We show that the problem of testing the feasibility of a given task set {T ¹,T ²,,T ⁿ} satisfyingP ₁₊₁=k_i p_i, wherek _i; is an integer 1 for 1i n–1, on a single processor is NP-hard in the strong sense, even if all tasks have the same arrival time. For task sets satisfyingP ⁱ⁺¹=K Pⁱ, whereK is an integer 2 for 1 i n–1 and all tasks have the same arrival time, we present linear-time (in the number of requests) optimal scheduling algorithms as well as linear-time (in the number of tasks, i.e.,n) algorithms for testing feasibility in both uniprocessor and multiprocessor systems. We also extend our results to more general task sets.     

The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

Three-valued representative systems

A representative system defined onn voters or propositionsi = 1,,n is a functionF: {1,0, -1} ⁿ {1,0, -1} which is monotonic (D E F(D) F(E)), unanimous (F(1,, 1) = 1), dual (F(-D) = -F(D)), and satisfies a positivity property which says that the set of all non-zero vectors in {1, 0, -1} ⁿ for whichF(D) = 0 can be partitioned into two dual subsets each of which has the property that ifD andE are in the subset thenD _i+E _i > 0 for somei. Representative systems can be defined recursively from the coordinate projectionsS _i (D) = D _i using sign functions, and in this format they are interpreted as hierarchical voting systems in which outcomes of votes in lower levels act as votes in higher levels of the system. For each positive integern, (n) is defined as the smallest positive integer such that all representative systems defined on {1, 0, -1} ⁿ can be characterized by(n) or fewer hierarchical levels. The function is nondecreasing inn, unbounded above, and satisfies(n) n–1 for alln. In addition,(n) = n–1 forn {1, 2, 3, 4}, and it is conjectured that does not continue to grow linearly asn increases.     

An efficient processing of a chain join with the minimum communication cost in distributed database systems

This paper investigates the optimization problem when executing a join in a distributed database environment. The minimization of the communication cost for sending data through links has been adopted as an optimization criterion. We explore in this paper the approach of judiciously using join operations as reducers in distributed query processing. In general, this problem is computationally intractable. A restriction of the execution of a join in a pre-defined combinatorial order leads to a possible solution in polynomial time. An algorithm for a chain query computation has been proposed in [21]. The time complexity of the algorithm isO(m ² n ²+m ³ n), wheren is the number of sites in the network, andm is the number of relations (fragments) involved in the join. In this paper, we firstly present a proof of the intuitively well understood fact—that the eigenorder of a chain join will be the best pre-defined combinatorial order to implement the algorithm in [21]. Secondly, we show a sufficient and necessary condition for a chain query with the eigenordering to be a simple query. For the process of the class of simple queries, we show a significant reduction of the time complexity fromO(m ² n ²+m ³ n) toO(mn+m ²). It is encouraging that, in practice, the most frequent queries belong to the category of simple queries. Editor: Peter Apers     

On reducing the number of states in a PDA

A transformation is presented which converts any pushdown automaton (PDA)M ₀ withn ₀ states andp ₀ stack symbols into an equivalent PDAM withn states and n ₀ /n² p ₀ stack symbols into an equivalent ofn, 1n ₀. This transformation preserves realtime behavior but not derterminism. The transformation is proved to be the best possible one in the following sense: for each choice of the parametersn ₀ + 1 stack symbols for any desired value realtime PDAM ₀ such that any equivalent PDAM (whether realtime or not) havingn states must have at least (n ₀ /n)² p₀ stack symbols. Furthermore, the loss of deterministic behavior cannot be avoided, since for each choice ofn ₀ andp ₀, there is a deterministic PDAM ₀ such that no equivalent PDAM with fewer states can be deterministic.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and MCS76-10076A01.     

On parsing two-level grammars

Summary Making use of the fact that two-level grammars (TLGs) may be thought of as finite specification of context-free grammars (CFGs) with infinite sets of productions, known techniques for parsing CFGs are applied to TLGs by first specifying a canonical CFG G — called skeleton grammar — obtained from the cross-reference of the TLG G. Under very natural restrictions it can be shown that for these grammar pairs (G, G) there exists a 1 — 1 correspondence between leftmost derivations in G and leftmost derivations in G. With these results a straightforward parsing algorithm for restricted TLGs is given.     

Exact 3-satisfiability is decidable in time <Emphasis Type="Italic">O</Emphasis>(2<Superscript>0.16254<Emphasis Type="Italic">n</Emphasis></Superscript>)

Let F=C ₁C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SATO(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SATO(2^0.16254n ).     

Cockpit cognition: Education,the military and cognitive engineering

The goals of public education, as well as conceptions of human intelligence and learning, are undergoing a transformation through the application of military-sponsored information technologies and information processing models of human thought. Recent emphases in education on thinking skills, learning strategies, and computer-based technologies are the latest episodes in the postwar military agenda to engineer intelligent components, human and artificial, for the optimal performance of complex technological systems. Public education serves increasingly as a human factors laboratory and production site for this military enterprise, whose high performance technologies and command and control paradigms have also played central roles in the emergence of the information economy.Our final hope is to develop the brain as a natural resource ... Human intelligence will be the weapon of the future.Luis Alberto MachadoThis paper will also appear, under the title Mental Material inCyborg Worlds: The Military Information Society, eds. Les Levidow and Kevin Robins, London: Free Association Press, (in press).     

A note on classes of complements and the LBA problem

Summary The complements of an AFL form an AFL if and only if is closed under length-preserving universal quantification. The complements of the context-sensitive languages form a principal AFL with a hardest set L ₁. The context-sensitive languages are closed under complementation if and only if L ₁ is context-sensitive.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and DCR74-15091     

Primality testing with fewer random bits

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses candidatesx ₁,x ₂, ...,x _k uniformly and independently at random from _n , and tests if any is a witness to the compositeness ofn. For either algorithm, the probabilty that it errs is at most 2^–k .In this paper, we study the error probabilities of these algorithms when the candidates are instead chosen asx, x+1, ..., x+k–1, wherex is chosen uniformly at random from _n . We prove that fork=[1/2log₂ n], the error probability of the Miller-Rabin test is no more thann ^–1/2+o(1), which improves on the boundn ^–1/4+o(1) previously obtained by Bach. We prove similar bounds for the Solovay-Strassen test, but they are not quite as strong; in particular, we only obtain a bound ofn ^–1/2+o(1) if the number of distinct prime factors ofn iso(logn/loglogn).     

The plane with parallel coordinates

By means ofParallel Coordinates planar graphs of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising cusp inflection point duality. The narrative ends with a preview of the corresponding results inR ^N .     

Notes on “A CUCH-machine: The automatic treatment of bound variables”

The method described in Ref. 1 does not always correctly establish the bonds between the variables. In fact, during the reduction to normal form of the -formula ((ty)(yy)) and of all those in which the same variable that is free in the left subformula of an application occurs bound in the right subformula, this variable is wrongly considered as bound. To prevent this, it is necessary to modify the levels assigned to the formulas in the -generation. We therefore give the correct -generation statements and the correct algorithm of the -generation.See Ref. 1.     

Minimization of norms and logarithmic norms by diagonal similarities

It is a commonly occurring problem to find good norms · or logarithmic norms (·) for a given matrix in the sense that they should be close to respectively the spectral radius (A) and the spectral abscissa (A). Examples may be the certification thatA is convergent, i.e. (A)A<1 or stable, i.e. (A)(A)<0. Often the ordinary norms do not suffice and one would like to try simple modifications of them such as using an ordinary norm for a diagonally transformed matrix. This paper treats this problem for some of the ordinary norms.

---

Minimisierung von Normen und Logarithmischen Normen durch Diagonale Transformationen

Zusammenfassung Ein oft vorkommendes praktisches Problem ist die Konstruktion von guten Normen · und logarithmischen Normen (·) für eine gegebene MatrixA. Mit gut wird dann verstanden, daß A den Spektralradius (A)=max |₁| und (A) die Spektralabszisse (A)=max Re _i gut approximieren. Beispiele findet man für konvergente Matrizen wo (A)A<1 gewünscht ist, und für stabile Matrizen wo (A)(A)<0 zu zeigen ist. Wir untersuchen hier, wie weit man mit Diagonaltransformationen und dengewöhnlichsten Normen kommen kann.