Cut point languages of markov DTOL systems

Letp satisfy 0 p < 1, then by (p) we denote the family of Markov DTOL languages with cut pointp. In this paper we present a complete classification of the collection of such families (p), 0 p < 1, showing that forms an infinite nondense hierarchy with (0) being its only accumulation point from below. Furthermore it is proved that each language in (p) can be expressed as a finite union of DDTOL languages.Work supported partially by the Natural Sciences and Engineering Research Council of Canada grants Nos. A-3590 and A-7700, and partially by Deutsche Forschungsgemeinschaft.     

Deterministic sequential functions

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions _P ^–1 , where _P consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions _P ^–1 , where is the family of endmarkers and is the family of removals of endmarkers. (The compositions are read from left to right). We also show that _P ^–1 is the family of the subsequential functions.This work was partially supported by the Esprit Basic Research Action Working Group No. 3166 ASMICS, the CNRS and the Academy of Finland     

Unification in partially commutative semigroups

Unification algorithms have been constructed for semigroups and commutative semigroups. This paper considers the intermediate case of partially commutative semigroups. We introduce classesN and of such semigroups and justify their use. We present an equation-solving algorithm for any member of the classN. This algorithm is relative to having an algorithm to determine all non-negative solutions of a certain class of diophantine equations of degree 2 which we call -equations. The difficulties arising when attempting to solve equations in members of the class are discussed, and we present arguments that strongly suggest that unification in these semigroups is undecidable.     

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.     

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.     

Property preserving abstractions for the verification of concurrent systems

We study property preserving transformations for reactive systems. The main idea is the use of simulations parameterized by Galois connections (, ), relating the lattices of properties of two systems. We propose and study a notion of preservation of properties expressed by formulas of a logic, by a function mapping sets of states of a systemS into sets of states of a systemS'. We give results on the preservation of properties expressed in sublanguages of the branching time -calculus when two systemsS andS' are related via (, )-simulations. They can be used to verify a property for a system by verifying the same property on a simpler system which is an abstraction of it. We show also under which conditions abstraction of concurrent systems can be computed from the abstraction of their components. This allows a compositional application of the proposed verification method.This is a revised version of the papers [2] and [16]; the results are fully developed in [28].This work was partially supported by ESPRIT Basic Research Action REACT.Verimag is a joint laboratory of CNRS, Institut National Polytechnique de Grenoble, Université J. Fourier and Verilog SA associated with IMAG.     

On a random Volterra integral equation

Summary Tsokos [12] showed the existence of a unique random solution of the random Volterra integral equation (*)x(t; ) = h(t; ) + _o ^t k(t, ; )f(, x(; )) d, where , the supporting set of a probability measure space (,A, P). It was required thatf must satisfy a Lipschitz condition in a certain subset of a Banach space. By using an extension of Banach's contraction-mapping principle, it is shown here that a unique random solution of (*) exists whenf is (, )-uniformly locally Lipschitz in the same subset of the Banach space considered in [12].     

Linear Interval Tolerance Problem and Linear Programming Techniques

In this paper, we consider the linear interval tolerance problem, which consists of finding the largest interval vector included in ([A], [b]) = {x R ⁿ | A [A], b [b], Ax = b}. We describe two different polyhedrons that represent subsets of all possible interval vectors in ([A], [b]), and we provide a new definition of the optimality of an interval vector included in ([A], [b]). Finally, we show how the Simplex algorithm can be applied to find an optimal interval vector in ([A], [b]).     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

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.     

Representation of Algebraic Functions As Power and Fractional Power Series of Special Type

A Maple procedure is described by means of which an algebraic function given by an equation f(x y) = 0 can be expanded into a fractional power series (Puiseux series)

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

Higher-Order and Modal Logic as a Framework for Explanation-Based Generalization

Certain tasks, such as formal program development and theorem proving, fundamentally rely upon the manipulation of higher-order objects such as functions and predicates. Computing tools intended to assist in performing these tasks are at present inadequate in both the amount of knowledge they contain (i.e., the level of support they provide) and in their ability to learn (i.e., their capacity to enhance that support over time). The application of a relevant machine learning technique—explanation-based generalization (EBG)—has thus far been limited to first-order problem representations. We extend EBG to generalize higher-order values, thereby enabling its application to higher-order problem encodings.Logic programming provides a uniform framework in which all aspects of explanation-based generalization and learning may be defined and carried out. First-order Horn logics (e.g., Prolog) are not, however, well suited to higher-order applications. Instead, we employ Prolog, a higher-order logic programming language, as our basic framework for realizing higher-order EBG. In order to capture the distinction between domain theory and training instance upon which EBG relies, we extend Prolog with the necessity operator of modal logic. We develop a meta-interpreter realizing EBG for the extended language, Prolog, and provide examples of higher-order EBG.     

A decision support tool for the diagnosis of breast cancer based upon Fuzzy ARTMAP

This paper presents research into the application of the fuzzy ARTMAP neural network model to the diagnosis of cancer from fine-needle aspirates of the breast. Trained fuzzy ARTMAP networks are differently pruned so as to maximise accuracy, sensitivity and specificity. The differently pruned networks are then employed in a cascade of networks intended to separate cases into certain and suspicious classes. This mimics the predictive behaviour of a human pathologist. The fuzzy ARTMAP model also provides symbolic rule extraction facilities and the validity of the derived rules for this domain is discussed. Additionally, results are provided showing the effects upon network performance of different input features and different observers. The implications of the findings are discussed.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

The liberalized δ-rule in free variable semantic tableaux

In this paper we have a closer look at one of the rules of the tableau calculus presented by Fitting [4], called the -rule. We prove that a modification of this rule, called the ⁺-rule, which uses fewer free variables, is also sound and complete. We examine the relationship between the ⁺-rule and variations of the -rule presented by Smullyan [9]. This leads to a second proof of the soundness of the ⁺-rule. An example shows the relevance of this modification for building tableau-based theorem provers.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

Maintaining Longest Paths Incrementally

Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O( + || log||) time and O() time respectively, where || and are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.