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 .     

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.     

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.     

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.     

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.     

A semantically complete extension sequence of the system $$\mathcal{L}^* $$

In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional calculus formal system . The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring processes are fuzzified. A sequence of new extensions { } of the system is proposed, and the completeness of is proved.     

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.     

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.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

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.     

Fast exponentiation using the truncation operation

Given an integerk, and anarbitrary integer greater than , we prove a tight bound of on the time required to compute with operations {+, –, *, /, ·, }, and constants {0, 1}. In contrast, when the floor operation is not available this computation requires (k) time. Using the upper bound, we give an time algorithm for computing log loga, for alln-bit integersa. This upper bound matches the lower bound for computing this function given by Mansour, Schieber, and Tiwari. To the best of our knowledge these are the first non-constant tight bounds for computations involving the floor operation.     

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.     

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.     

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.     

The Complexity of Learning According to Two Models of a Drifting Environment

We show that a bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy , where c > 0 is a constant; this matches a known necessary condition to within a constant factor. We establish a sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor. We provide a relatively simple proof of a bound of + on the sample complexity of agnostic learning in a fixed environment.     

Two-Parameter Discrete Systems over a Residue Ring and Their Properties

A class of two-parameter discrete systems defined on the ring of class of residues of integers modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability.     

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.     

A semantics for a class of non-deterministic and causal production system programs

We define a class of function-free rule-based production system (PS) programs that exhibit non-deterministic and/or causal behavior. We develop a fixpoint semantics and an equivalent declarative semantics for these programs. The criterion to recognize the class of non-deterministic causal (NDC) PS programs is based upon extending and relaxing the concept of stratification, to partition the rules of the program. Unlike strict stratification, this relaxed stratification criterion allows a more flexible partitioning of the rules and admits programs whose execution is non-deterministic or causal or both. The fixpoint semantics is based upon a monotonic fixpoint operator which guarantees that the execution of the program will terminate. Each fixpoint corresponds to a minimal database of answers for the NDC PS program. Since the execution of the program is non-deterministic, several fixpoints may be obtained. To obtain a declarative meaning for the PS program, we associate a normal logic program with each NDC PS program. We use the generalized disjunctive well-founded semantics to provide a meaning to the normal logic program Through these semantics, a well-founded state is associated with and a set of possible extensions, each of which are minimal models for the well-founded state, are obtained. We show that the fixpoint semantics for the NDC PS programs is sound and complete with respect to the declarative semantics for the corresponding normal logic program .This research is partially sponsored by the National Science Foundation under grant IRI-9008208 and by the Institute for Advanced Computer Studies.     

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.