Super-pattern matching

Some recognition problems are either too complex or too ambiguous to be expressed as a simple pattern matching problem using a sequence or regular expression pattern. In these cases, a richer environment is needed to describe the patterns and recognition techniques used to perform the recognition. Some researchers have turned to artificial-intelligence techniques and multistep matching approaches for the problems of gene recognition [5], [7], [18], protein structure recognition [13], and on-line character recognition [6]. This paper presents a class of problems which involve finding matches to patterns of patterns, orsuper- patterns, given solutions to the lower-level patterns. The expressiveness of this problem class rivals that of traditional artificial-intelligence characterizations, and yet polynomial-time algorithms are described for each problem in the class.This work was supported in part by the National Institute of Health under Grant ROI LM04960 and by the Aspen Center for Physics.     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

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.     

Type inference with non-structural subtyping

We present an O(n³) time type inference algorithm for a type system with a largest type, a smallest type , and the usual ordering between function types. The algorithm infers type annotations of least shape, and it works equally well for recursive types. For the problem of typability, our algorithm is simpler than the one of Kozen, Palsberg, and Schwartzbach for type inferencewithout . This may be surprising, especially because the system with is strictly more powerful.     

Propositional truth maintenance systems: Classification and complexity analysis

Truth maintenance (TM) has been an active area of artificial intelligence (AI) research in recent years. In particular, truth maintenance systems (TMSs) in many variant types have become popular mechanisms for implementing nonmonotonic inference systems. Knowledge about the computational foundations of a TMS is indispensable for their use. We present a classification of computational complexity of tasks performed by basic existing TMS types. Our results include the proof ₂ ^p -completeness of the clause maintenance system's computation task. This is the first problem in AI proved to be ₂ ^p -complete. It is likely to provide a basis for proving ₂ ^p -completeness of other problems in logic and AI. As part of the proof, we prove the ₂ ^p -completeness of the generalized node deletion problem, one of the first natural graph problems to be complete for any one of the classes _i ^p , forp>1. We also prove the polynomial equivalence of Boolean Constraint Propagation-based (logic-based) approaches (LTMSs) and justification-based approaches (JTMSs) to TM, and exhibit efficient algorithms for transforming an LTMS into a JTMS and vice versa.     

The connection between an event structure semantics and an operational semantics forTCSP

The relation between an operational interleaving semantics forTSCP based on a transition system and a compositional true concurrency semantics based on event structures is studied. In particular we extend the consistency result of Goltz and Loogan [15] forTCSP processes without recursion to the general case. Thus we obtain for everyTCSP processP that its operational meaningO(P) and the interleaving behaviourO( M3P3) which is derived from the event structureM3P3 associated withP are bisimilar.     

Complexity of the word problem for commutative semigroups of fixed dimension

Summary In this paper we investigate the computational complexity of the word problem for commutative semigroups of fixed dimension. It is shown that for commutative semigroups of dimension k, k 6, the word problem is complete for symmetric linear space, providing another complete problem for this symmetric complexity class. We also show that in the case of one generator, the word problem is solvable in polynomial time.     

Local accessibility,local reachability,and representations of compact groups

In this paper we consider the local controllability problem for nonlinear control systems, or as we prefer to call it, the local reachability problem. We introduce the action of a compact group on the system, and define what it means for the system to be invariant under the group action. Our principal result gives sufficient conditions, in terms of the group action, in order that a locally accessible system is also locally reachable. The technique used is a generalization of one first introduced by P. Brunovsky for odd systems invariant under a certainZ ₂ action. We give both geometric and group representational interpretations of our conditions, and provide examples of our conditions applied to certain even systems which do not satisfy Brunovsky's conditions.     

Parallel geometric algorithms on a mesh-connected computer

We show that a number of geometric problems can be solved on a n × n mesh-connected computer (MCC) inO(n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires (n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.This work was supported in part by the National Science Foundation under Grant DCR 8420814. A preliminary version was presented in the 1987 FJCC, Dallas, TX.     

Synchronous and Asynchronous Interval Newton-Schwarz Methods for a Class of Large Systems of Nonlinear Equations

We introduce a class of parallel interval arithmetic iteration methods for nonlinear systems of equations, especially of the type Ax+(x) = f, diagonal, in R ^N . These methods combine enclosure and global convergence properties of Newton-like interval methods with the computational efficiency of parallel block iteration methods: algebraic forms of Schwarz-type methods which generalize both the well-known additive algebraic Schwarz Alternating Procedure and multisplitting methods. We discuss both synchronous and asynchronous variants. Besides enclosure and convergence properties, we present numerical results from a CRAY T3E.     

Model elimination without contrapositives and its application to PTTP

We give modifications of model elimination that do not necessitate the use of contrapositives. These restart model elimination calculi are proven sound and complete, and their implementation by PTTP is depicted. The corresponding proof procedures are evaluated by a number of runtime experiments, and they are compared to other well-known provers. We relate our results to other calculi, namely, the connection method, modified problem reduction format, and near-Horn Prolog.A shorter version will appear under the title Model Elimination Without Contrapositives inProc. of the CADE'94.     

A hypergraph model for constraint logic programming and applications to bus drivers' scheduling

In a previous paper, a hypergraph model for the satisfiability of Datalog formulas was proposed. Here, we extend that approach in order to deal with a class ofconstraint logic programming (CLP) formulas, that is, Datalog formulas in the presence of constraints. A CLP formula is represented by means of a weighted hypergraph and the problem of evaluating this formula is reduced to a sequence of shortest path computations on hypergraphs. To evaluate the performance of this approach, the bus drivers' scheduling problem is formulated as the problem of checking the satisfiability of a CLP formula and it is solved by means of the hypergraph-based algorithm embedded within a local search procedure. Preliminary experimental results are quite encouraging and suggest that the proposed approach may provide an efficient way to tackle hard real-life combinatorial problems.This research was partially supported by the Progetto Finalizzato Trasporti 2 of the Italian National Research Council, under Contract No. 91.02479.PF74.     

Ramsey numbers and an approximation algorithm for the vertex cover problem

Summary We show two results. First we derive an upper bound for the special Ramsey numbers r _k(q) where r _k(q) is the largest number of nodes a graph without odd cycles of length bounded by 2k+1 and without an independent set of size q+1 can have. We prove The proof is constructive and yields an algorithm for computing an independent set of that size. Using this algorithm we secondly describe an O(¦V¦·¦E¦) time bounded approximation algorithm for the vertex cover problem, whose worst case ratio is , for all graphs with at most (2k+3) ^k (2k+2) nodes (e.g. 1.8, if ¦V¦146000).     

Stability in the Combinatorial Vector Optimization Problems

Consideration was given to the vector (multicriteria) problem on the system of subsets of a finite set. In the case of linear subtests, a formula of the stability radius of efficient solution in the metric l ₁ was obtained. For the vector problem with subtests of the form MINMAX MODUL, the necessary and sufficient stability conditions were established (retention or contraction of the Pareto set for small variations in the source data).     

Dynamic half-space range reporting and its applications

We consider the half-space range-reporting problem: Given a setS ofn points in ^d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n ^d/2 and an arbitrarily small positive constant , we achieveO(m ¹⁺) space and preprocessing time, O((n/m ^d/2 logn+k) query time, and O(m¹⁺n) amortized update time (d 3). We present, among others, the following applications: an O(n¹⁺)-time algorithm for computing convex layers in ³, and an output sensitive algorithm for computing a level in an arrangements of planes in ³, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees.     

Simple learning algorithms using divide and conquer

This paper investigates what happens when a learning algorithm for a classC attempts to learn target formulas from a different class. In many cases, the learning algorithm will find a bad attribute or a property of the target formula which precludes its membership in the classC. To continue the learning process, we proceed by building a decision tree according to the possible values of this attribute (divide) and recursively run the learning algorithm for each value (conquer). This paper shows how to recursively run the learning algorithm for each value using the oracles of the target.We demonstrate that the application of this idea on some known learning algorithms can both simplify the algorithm and provide additional power to learn more classes. In particular, we give a simple exact learning algorithm, using membership and equivalence queries, for the class of DNF that is almost unate, that is, unate with the addition ofO (logn) nonunate variables and a constant number of terms. We also find algorithms in different models for boolean functions that depend onk terms.     

Parallel integer sorting using small operations

We consider the problem of sortingn integers in the range [0,n ^c -1], wherec is a constant. It has been shown by Rajasekaran and Sen [14] that this problem can be solved optimally inO(logn) steps on an EREW PRAM withO(n) n -bit operations, for any constant >O. Though the number of operations is optimal, each operation is very large. In this paper, we show thatn integers in the range [0,n ^c -1] can be sorted inO(logn) time withO(nlogn)O(1)-bit operations andO(n) O(logn)-bit operations. The model used is a non-standard variant of an EREW PRAMtthat permits processors to have word-sizes ofO(1)-bits and (logn)-bits. Clearly, the speed of the proposed algorithm is optimal. Considering that the input to the problem consists ofO (n logn) bits, the proposed algorithm performs an optimal amount of work, measured at the bit level.This work was partially supported by The Northeast Parallel Architectures Center (NPAC) at Syracuse University, Syracuse, NY 13244 and The Rome Air Development Center, under contract F30602-88-D-0027.     

Priority as extremal probability

We extend the stratified model of probabilistic processes to obtain a very general notion ofprocess priority. The main idea is to allow probability guards of value 0 to be associated with alternatives of a probabilistic summation expression. Such alternatives can be chosen only if the non-zero alternatives are precluded by contextual constraints. We refer to this model as one of extremal probability and to its signature asPCCS . We providePCCS with a structural operational semantics and a notionof probabilistic bisimulation, which is shown to be a congruence. Of particular interest is the abstractionPCCS ofPCCS in which all non-zero probability guards are identified.PCCS represents a customized framework for reasoning about priority, and covers all features of process algebras proposed for reasoning about priority that we know of.A preliminary version of this paper appeared inProceedings of CONCUR '90 — First International Conference on Concurrency Theory, Vol. 458 of the Springer-Verlag seriesLecture Notes in Computer Science, pp. 456–466, Aug. 1990. The research of Scott Smolka was supported in part by NSF Grants CCR-9120995, CCR-9208585 and CCR-9505562; and AFOSR Grants F49620-93-1-0250, F49620-95-1-0508 and F49620-96-1-0087.     

The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

MEG-Eliminations

The basic disadvantage of the algorithms of EG-eliminations [1] is that the degrees of elements of the polynomial matrix being used and the coefficients of these elements grow. The progress in overcoming this difficulty is associated with the use of modular approaches. The paper describes modularization of EG-eliminations and a modified elimination scheme based on that modularization (quasi-modular algorithm).