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.     

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.     

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.     

Computational Finite-Element Schemes for Optimal Control of an Elliptic System with Conjugation Conditions

New optimal control problems are considered for distributed systems described by elliptic equations with conjugate conditions and a quadratic minimized function. Highly accurate computational discretization schemes are constructed for the case where a feasible control set coincides with the full Hilbert space of controls.     

Stability of the Logistic Population Model with Delayed Environmental Response

The population dynamics model , was considered. For this model with uniform distribution of delays and a _n = 0, nonnegativeness and convexity of the sequence a _k (0 k n) was shown to be the sufficient stability condition. Therefore, there is no need to constrain the reproduction rate and the mean delay .     

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 .     

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.     

On the rational summation problem

A partial proof of the van Hoeij-Abramov conjecture on the algorithm of definite rational summation is given. The results obtained underlie an algorithm for finding a wide class of sums of the form .Translated from Programmirovanie, Vol. 31, No. 2, 2005.Original Russian Text Copyright © 2005 by Tsarev.     

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.     

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.     

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.     

Conditions for Instability of One Class of Nonlinear Nonautomomous Dynamic Systems

Consideration was given to the conditions for instability of the equilibrium states of a nonlinear nonautonomous dynamic systems obeying an ordinary vector differential equation of arbitrary order whose right-hand side satisfies the following conditions: (i) for any t 0, div 0$$ " align="middle" border="0"> almost everywhere on the set H that is a neighborhood of the equilibrium point of the system and (ii) at any point . The equilibrium states of such systems can be both stable and unstable. For one class of these systems, sufficient instability conditions were given, which enables one to carry out studies using only the information about the right-hand side of the system.     

Upon some continuous prediction algorithms. I

Three difference-differential processes operating upon an initial value function Φ (μ) and yielding a sequence of approximations to are described. The processes are confluent analogues of an algorithm related to Romberg's extrapolation procedure, of the π-algorithm, and of the ε-algorithm. It is shown that these processes can be modified to yield approximations to the integral , and that in certain circumstances this integral can be evaluated by a process of repeated differentiation involving the function ψ(μ). Discrete algorithms for approximating , for which it is assnmed, that values of the successive derivatives of the function Φ (μ) are available, are described. It is shown that these algorithms can be applied to the evaluation of the integral , it being assumed that the values of the successive derivatives of the function ψ(μ) are available. A number of examples in which closed expressions for the transformed estimates can be derived are discussed. Algol procedures for implementing the discrete algorithms are given In Memoriam H. Rutishauser     

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.     

Calcolo approssimato per difetto e per eccesso di integrali

Sommario Viene fornito un metodo in cui si fa uso di formule di quadratura generalizate per il calcolo approssimato per difetto e per eccesso dell'integrale ..u(x)dx doveu(x)∈AC ⁿ⁻¹ [0,1];u ⁽ⁿ⁾ (x) è limitata inferiormente;p(x)=1 oppurep(x)∈L [0, 1],p(x)>-0 e . Vengono poi dati alcuni esempi numerici.

---

A method, using generalized quadrature formulae, is given for approximate evaluation from below and above of whereu(x)∈A C ⁿ⁻¹ [0,1],u ⁽ⁿ⁾ (x) lower bounded,p(x)=1 orp(x)∈L [0,1],p(x)≥0, . Some numerical examples are given.

---

---

Lavoro eseguito nell'ambito del gruppo di ricerca G.N.A.F.A. del C.N.R.     

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.     

Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time

The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language learning algorithm with respect to its total learning time. Pattern languages have been introduced by Angluin (1980) and are defined as follows: Let be any non-empty finite alphabet containing at least two elements. Furthermore, let be an infinite set of variables such that . Patterns are non-empty strings over . L(π), the language generated by pattern π, is the set of strings which can be obtained by substituting non-null strings from for the variables of the pattern π. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages in the limit from text. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken by the algorithm until convergence. For every pattern π containing k different variables it is shown that the total learning time is in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of with respect to the uniform distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.