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.     

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 .     

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.     

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.     

On the rank of certain finite fields

In the present paper we shall show that the rank of the finite field regarded as an -algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of -rational points of an algebraic curve of genus 2 over . Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound . For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound.     

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.     

Determination of the roots and of the global extremum of a lipschitz function

Conclusion The obvious deficiency of the method (1.3), (1.9) is the possible difficulty of the operation . In connection with this one can note that all the above given statements remain valid if the number is replaced by some positive lower bound of |f(t _k ,x)| on .In computational methods, the presence of the Lipschitz constant is considered as a deficiency. In connection with this we can note that the Lipschitz constant L can be replaced by any of its upper estimates. For example, for a differentiable function f(z) one can take .Translated from Kibernetika, No. 2, pp. 71–74, March–April, 1987.     

Structural properties for feasibly computable classes of type two

This paper treates classes in the polynomial hierarchy of type two, , that were first developed by Townsend as a natural extension of the Meyer-Stockmeyer polynomial hierarchy in complexity theory. For these classes, it is discussed whether each of them has the extension property and the three recursion-theoretic properties: separation, reduction, and pre-wellordering. This paper shows that every 0$$ " align="middle" border="0"> , lacks the pre-wellordering property by using a probabilistic argument on constant-depth Boolean circuits. From the assumption NP = coNP it follows by a pruning argument that has the separation and extension properties.     

A note on relativized log space

It is shown that there is a recursive oracleD such that, thereby answering an open question of Ladner and Lynch [5]. Here and denote the class of languages accepted in deterministic, respectively nondeterministic, space logn. This work was supported by NSF Grant MCS-8001963.     

Universal asynchronous iterative arrays of Mealy automata

Summary Asynchronous two-dimensional iterative arrays of automata will be introduced where the underlying automata are not of Moore-type but of Mealy-type. We will prove that there exists a Mealy automaton, , with only two states and one input and output for each of its four distinguished directions, such that any given Mealy-automaton can be realized by an iterative array with only for its component-machines. It is known that loop-free nets cannot be as powerful as Mealy automata; however, we will show that any Mealy automaton can be realized by a network, N, with very restrictive component machines, where no signal may pass a loop in N. Using this fact asynchronous iterative arrays can be built up with one component machine, such that any given Mealy automaton can be realized under the restriction that no signal passes a loop more than once. contains only four states and one input and output for each direction.     

The inf-sup condition for low order elements on anisotropic meshes

On a large class of two-dimensional anisotropic meshes, the infsup condition (stability) is proved for the triangular and quadrilateral finite element pairs suggested by Bernardi/Raugel and Fortin. As a consequence the pairs , and turn out to be stable independent of the aspect ratio of the elements. Both the visit of the first author in Valenciennes and the visit of the second author in Chemnitz were financed by the DFG (German Research Foundation), Sonderforschungsbereich 393.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems

In this paper, we investigate the problem of scheduling soft aperiodic requests in systems where periodic tasks are scheduled on a fixed-priority, preemptive basis. First, we show that given any queueing discipline for the aperiodic requests, no scheduling algorithm can minimize the response time of every aperiodic request and guarantee that the deadlines of the periodic tasks are met when the periodic tasks are scheduled on a fixed-priority, preemptive basis. We then develop two algorithms: Algorithm is locally optimal in that it minimizes the response time of the aperiodic request at the head of the aperiodic service queue. Algorithm is globally optimal in that it completes the current backlog of work in the aperiodic service queue as early as possible.     

Integration of a linear many-valued mapping of a special type

We consider the solvability of the integral equation for the unknown set W. A. bound of the integral is given for some class of sets M. The results are applied in differential games.Translated from Kibernetika, No. 3, pp. 90–95, May–June 1990.     

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.     

Complexity of optimal scheduling problems with three jobs

We consider the time-optimal scheduling problemn/m/J of n jobs with fixed routes on m machines. The problem3/m/J/ with identical routes and the problem3/5/J/ are shown to be NP-hard. Similar results are obtained for the problem of minimizing the mean processing time of three jobs on m machines.Translated from Kibernetika, No. 5, pp. 50–54, September–October, 1990.     

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.     

Finding tree patterns consistent with positive and negative examples using queries

This paper is concerned with the problem of finding a hypothesis in consistent with given positive and negative examples. The hypothesis class consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages. Especially, we consider the problem from the point of view of the consistency problem for . The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete for many hypothesis spaces. In this paper, the problem for the class is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result, we have that the consistency problem for is solved in polynomial time using membership queries. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.