A short note on simultaneous splitting

We show that for any alphabet there is a setL ^* such that ifC is any infinite co-infinite context-free language over , thenL splitsC (i.e., each ofL C,L , C, and is infinite).Preparation of this paper was supported in part by the National Science Foundation under Grant No. MCS77-11360.     

Solving A\underline x =\underline b Using a Modified Conjugate Gradient Method Based on Roots of A

We consider the modified conjugate gradient procedure for solving A = in which the approximation space is based upon the Krylov space associated with A ^1/p and , for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in . We discuss the implications of the quickly accumulating effect of an error in in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests.     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .     

Definability of Polyadic Lifts of Generalized Quantifiers

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type < 1 >.We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.     

A Note on the Rational Closure of Knowledge Bases with Both Positive and Negative Knowledge

The notion of the rational closure of a positive knowledge base K of conditional assertions | (standing for if then normally ) was first introduced by Lehmann (1989) and developed by Lehmann and Magidor (1992). Following those authors we would also argue that the rational closure is, in a strong sense, the minimal information, or simplest, rational consequence relation satisfying K. In practice, however, one might expect a knowledge base to consist not just of positive conditional assertions, | , but also negative conditional assertions, _i (standing for not if then normally . Restricting ourselves to a finite language we show that the rational closure still exists for satisfiable knowledge bases containing both positive and negative conditional assertions and has similar properties to those exhibited in Lehmann and Magidor (1992). In particular an algorithm in Lehmann and Magidor (1992) which constructs the rational closure can be adapted to this case and yields, in turn, completeness theorems for the conditional assertions entailed by such a mixed knowledge base.     

Algorithmic properties of maximal orders in simple algebras over Q

This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P co N P. As consequences, we obtain that the problem of deciding if is isomorphic to a full matrix algebra over the ground field and the problem of deciding if is a skewfield both belong toN P co N P. These results answer two questions raised in [25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields.     

Decision procedures for elementary sublanguages of set theory

In this paper we prove the decidability of the class of unquantified formulae of set theory involving the operators , , , \, {·}, pred _< and the predicates =, , , Finite, where pred _<(s) denotes the collection of all sets having rank strictly less than the rank of s.This work generalizes and combines earlier results published in the same series of papers.This work has been partially supported by ENI and ENIDATA within the AXL project.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple (logn) algorithm for the distance transform with respect to theL ₁-metric, an (log² n) algorithm for the transform with respect to theL -metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time (log³ n).This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1-1, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Modelling Asynchrony with a Synchronous Model

The I/O automaton paradigm of Lynch and Tuttle models asynchrony through an interleaving parallel composition. The recognition that such interleaving models in fact can be viewed as special cases of synchronous parallel composition has been very limited. Let be any set of finite-state I/O automata drawing actions from a fixed finite set containing a subset . In this article we establish a translation T : to a class of -automata closed under a synchronous parallel composition, for which T is monotonic with respect to implementation relative to , and linear with respect to composition. Thus, for A¹, ..., A, B¹, ..., B and A = A¹ ... A, B = B¹ ... B, if is the set of actions common to both A and B, then A implements B (in the sense of I/O automata) if and only if the -automaton language containment (T(A¹) ... T(A)) (T(B¹) ... T(B)) obtains, where denotes the interleaving parallel composition on and denotes the synchronous parallel composition on . For the class , we use the L-process model of -automata. This result enables one to verify systems specified by I/O automata through model-checkers such as COSPAN or SMV, that operate on models with synchronous parallel composition. The translation technique generalizes to other interleaving models, although in each case, the translation map must match the specific model.     

Generating Boolean \mu-expressions

In this paper, we consider the class of Boolean -functions, which are the Boolean functions definable by -expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formulaE into an equivalent -expression-if possible-in time linear in E times , where E is the size ofE andn _m is the number of variables that occur more than once inE. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing -functions fromk-formulas [17]. Furthermore, we show that recognizing Boolean -functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Records of turing machines

Suppose a Turing machine is equipped with an extra tape. At each step of a computation being performed, it prints symbol read move symbol symbol printed on a square of the extra tape. It then moves the extra tape one square to the left. This procedure yields arecord of the computation.If is a finite alphabet, let be the set of triples (a, b, c) wherea ,c , andb {–1, 0, 1}. We will characterize those sequences of symbols of that are records of computations of Turing machines.This research was supported in part by AFOSR Grant GP-68-1402.     

An Algebraic Approach to Propositional Fuzzy Logic

We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield , and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields.     

Directional differentiation of marginal functions in mathematical programming problems

We consider regular mathematical programming problems of the form f(x, y) inf, y F(x), x Rⁿ, where F(x) = {y R^m h_i| (x, y) 0, , h_i (x, y) = 0, . The directional derivatives offunctions (x) = inf{f(x, y)|y F(x)} are estimated.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–77, November–December, 1991.     

Biologically Inspired Autonomous Rover Control

Robotic missions beyond 2013 will likely be precursors to a manned habitat deployment on Mars. Such missions require robust control systems for long duration activities. Current single rover missions will evolve into deployment of multiple, heterogeneous cooperating robotic colonies. This paper describes the map-making memory and action selection mechanism of BISMARC ( iologically nspired ystem for ap-based utonomous over ontrol) that is currently under development at the Jet Propulsion Laboratory in Pasadena, CA (Huntsberger and Rose, Neutral Networks, 11(7/8):1497–1510). BISMARC is an integrated control system for long duration missions involving robots performing cooperative tasks.     

Exact Linear Thermodynamic Evolution Equations from the Robertson Formalism

A linear evolution equation for a thermodynamic variable F, odd under time-reversal, is obtained from the exact equation derived by Robertson from the Liouville equation for the information-theoretic phase-space distribution. One obtains an exact expression for , the relaxation time for F. For very short , is time-independent for t > if C(t) F{exp(-i t)}Fo, the equilibrium time correlation, decays exponentially for t > . is the Liouville operator. So long as C(t) is such that decays rapidly to a steady-state value, the t limit of agrees with the fluctuation-dissipation theorem in applications to fluid transport.     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Generalized lowness and highness and probabilistic complexity classes

We introduce generalized notions of low and high complexity classes and study their relation to structural questions concerning bounded probabilistic polynomial-time complexity classes. We show, for example, that for a bounded probabilistic polynomial-time complexity class =BP _k ^P ,L =H implies that the polynomial hierarchy collapses to . This extends Schöning's result for = _k ^P (L andH are the low and high sets defined by ). We also show, with one exception, that containment relations between the bounded probabilistic classes and the polynomial hierarchy are preserved by their low and high counterparts.LBPP andLBPNP are characterized asNP BPP andNP co-BPNP, respectively. These characterizations are then used to recover Boppana, Hastad, and Zachos's result that if co-NP BPNP, then the polynomial hierarchy collapses toBPNP, and Ko's result that ifNP BPP, then the polynomial hierarchy collapses toBPP.     

Optimization of rotor blades for combined structural,dynamic, and aerodynamic properties

A helicopter is intrinsically interdisciplinary due to the close coupling among aerodynamics, dynamics, and the blade structural details. Therefore a design optimization with proper interactions among appropriate disciplines (such as structure, dynamics, and aerodynamics) can offer significant benefit to improve rotor performance. This paper studies the integration of structure, dynamics, and aerodynamics in design optimization of helicopter rotor blades. The optimization is performed to minimize the rotor power required and to satisfy design requirements from structure (minimum blade weight and safe stress margin and fatigue life) and dynamics (proper placement of blade natural frequencies and free of flutter). An effort is made to formulate an effective strategy for combining these various requirements in the optimization process. The paper also presents a way for an intelligent phasing of this interdisciplinary optimization to overcome the hurdles due to conflicting demands on the design variables which arise from different disciplines.Notation nondimensional leading edge mass size, = a/R - C _T rotor thrust coefficient - C _P rotor power coefficient - nondimensional chord, =c/R - nondimensional lumped mass size, =d/R - F(x) objective function - G _j (x) j-th inequality constraint function - H _j (x) j-th equality constraint function - R blade radius, meters - nondimensional blade radial coordinate, =r/R - nondimensional web thickness, =s ₁/R - nondimensional web thickness, =s ₂/R - t nondimensional flange thickness, =t/R - x vector of design variables - x _i i-th component of vector of design variables - blade pitch angle     

Finiteness in Infinite-Valued Łukasiewicz Logic

In this paper we deepen Mundici's analysis on reducibility of the decision problem from infinite-valued ukasiewicz logic to a suitable m-valued ukasiewicz logic _m , where m only depends on the length of the formulas to be proved. Using geometrical arguments we find a better upper bound for the least integer m such that a formula is valid in if and only if it is also valid in _m. We also reduce the notion of logical consequence in to the same notion in a suitable finite set of finite-valued ukasiewicz logics. Finally, we define an analytic and internal sequent calculus for infinite-valued ukasiewicz logic.