Search

This paper studies a distributed algorithm for finding a common fixed point of a family of m > 1 nonlinear maps M i : ℝn → ℝn assuming that each map is strongly quasi-nonexpansive, and that at least one such common fixed point exists. A common fixed point is simultaneously and recursively computed by m agents assuming that each agent i knows only M i , the current estimates of the fixed point generated by its neighbors, and nothing more. Neighbor relationships are described by a time-varying directed graph ℕ(t) whose vertices correspond to agents and whose arcs depict neighbor relationships. It is shown that for any sequence of repeatedly jointly strongly connected neighbor graphs ℕ(t), t ∈ {1, 2, …}, the algorithm causes all agents' estimates to converge to a common fixed point of M i , i ∈ {1, 2, …, m}.

A distributed algorithm is described for finding a common fixed point of a family of m > 1 nonlinear maps M i : Rn → Rn assuming that each map is a paracontraction. The common fixed point is asynchronously computed in real time by m agents assuming each agent i knows only M i , the current estimates of the fixed point generated by its neighbors, and nothing more. Each agent recursively updates its estimate of the fixed point at its own event times, by utilizing estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph N(t) whose vertices correspond to agents and whose arcs depict neighbor relations.

The fixed point theorems on partially ordered quasi-metric space has proved in previous work. In this manuscript, we forward to present a fixed point theorems into the same space by using a generalized altering distance function into its contractive mapping. This result expands other results from the references.

The existing artificial intelligence techniques for games of Go have made remarkable achievements. However, the strongest AI for Go does not have a deterministic search capability. To address this issue, we introduce the model checking technique to the field of Go algorithms. First, we use an Alternating Finite Automaton (AFA) to establish a formal model for Go, and we employee a formula of Alternating-time Temporal Logic (ATL) to formalize win conditions. On the basis of it, the Go problem is mapped to the model checking problem between the ATL formula and the AFA. By employing the Ordered Binary Decision Diagram (OBDD) technique, we obtain a method for computing the least fixed point to implicitly perform model checking, in order to avoid the huge state space of Go that cause insufficient memory. As shown in the simulation results, the symbolic model checking can efficiently conduct some deterministic searches in the state space of Go.

This paper proposes the Split Common Fixed Point problem, this type of problem requires finding a type of operator's Common Fixed Point in space, meanwhile, and the image of the Fixed Point under the Linear Transformation is also the Common Fixed Point of another type of operator's image in space. This paper also provides the solution to solve the split common fixed point problem by using the directed operators.

The semantics of fixed point constructions is commonly defined in terms of iteration sequences. For example, the least fixed point of a monotone operator consists of all points which eventually appear in the approximations computed iteratively. We take this temporal reading as the starting point and develop a systematic approach to temporal definitions over iteration sequences. As a result, we propose an extension of first-order predicate logic with an iterative operator, in which iteration steps may be accessed by temporal logic formulae. We show that proposed logic FO+TAI subsumes virtually all known deterministic fixed point extentions of first-order logic as its natural fragments. On the other hand we show that over finite structures FO+TAI has the same expressive power as FO+PFP (FO with partial fixed point operator), but in many cases providing with more concise definitions. Finally, we show that the extension of modal mu-calculus with the temporal access leads to the more expressive logic closed under assume-guarantee specifications operator

Based on the fixed point theory of the complete lattice, we propose a theoretical framework on how to find out the association rule in a transactional datebase. The results show that finding a closed item set is a process of establishing a Galois contact and mining all the closed item sets is the way to find out all the fixed points of its closed Galois operator.

For a finite lattice (D I , ≤) consisting of integer points in an n-dimensional box D of Rn and an increasing mapping ψ from D I into itself, the well-known Tarski's fixed point theorem asserts that there exists a point x* ∈ D I such that ψ(x*) = x*, which is a fixed point of ψ in D I and has applications in supermodular games from economic analysis. To compute such a fixed point, an arbitrary starting simplicial algorithm is developed in this paper through an introduction of an integer labeling rule and an application of a triangulation of Rn. The algorithm consists of two phases, one of which forms a variable dimension pivoting procedure and the other a full-dimensional pivoting procedure. Starting from an arbitrary integer point in D, the algorithm interchanges from one phase to the other, if necessary, and follows a finite simplicial path that leads to a fixed point of ψ in D I . The interchanging step is essential to ensure that the algorithm converges to a fixed point. A significant advantage of the algorithm is its arbitrary starting feature, which can certainly benefit from any information on where a fixed point may be found.

The abstract monotone iterative technique is well know and very important for applications to a variety of situations. With partial order defined in metric space, the purpose of this paper is to discuss the existence of coupled fixed point for mixed monotone mapping pairs. The results are quite different from the results in recent references. The paper also gives two examples to illustrate the theorems which indicate that the coupled fixed point may not be unique.

We deal with a relational model for the demonic semantics of programs. The demonic semantics of a while loop is given as a fixed point of a function involving the demonic operators. This motivates us to investigate the fixed points of these functions. We give the expression of the greatest fixed point with respect to the demonic ordering ({\it demonic inclusion}) of the semantic function. We prove that this greatest fixed coincides with the least fixed point with respect to the usual ordering ({\it angelic inclusion}) of the same function. This is followed by an example of application.

In this paper a further step towards a novel approach to adaptive nonlinear control developed at Budapest Tech in the past few years is reported. Its main advantage in comparison with the complicated Lyapunov function based techniques is that it is based on simple geometric considerations on the basis of which the control task can be formulated as a fixed point problem for the solution of which a contractive mapping is created that generates an iterative Cauchy sequence for single input-single output (SISO) systems. Consequently it converges to the fixed point that is the solution of the control task. In the formerly developed approaches for monotone increasing or monotone decreasing systems the proper fixed points had only a finite basin of attraction outside of which the iteration might become divergent. The here sketched potential solutions apply a special function built up of the ldquoresponse functionrdquo of the excited system under control and of a few parameters. This function has almost constant value apart from a finite region in which it has a ldquowrinklerdquo in the vicinity of the desired solution that is the ldquoproperrdquo fixed point of this function. By the use of an affine approximation of the response function around the solution it is shown that at one of its sides this fixed point is repulsive, while at the opposite side it is attractive. It is shown, too, that at the repulsive side another, so called ldquofalserdquo fixed point is present that is globally attractive, with the exception of the basin of attraction of the ldquoproperrdquo one. This structure is advantageous because (a) no divergence can occur in the iteration, (b) the convergence to the ldquofalserdquo value can easily be detected, and (c) by using some ancillary tricks in the most of the cases the solution can be kicked from the wrong fixed point into the basin of attraction of the ldquoproper onerdquo. In the paper preliminary calculations are presented.

In this paper, a two populations intergrowth system with two positive parameters is considered. By using the Krasnoselskii's fixed point theorem, the existence results of periodic solutions are obtained. The obtained results are mainly dependent on the parameters.

In this article, firstly, the necessary and sufficient condition of upper (lower) completeness is attained. Secondly, the notion of upper (lower) contraction of a mapping between quasi-metric spaces is put forward. Considering the asymmetric of quasi-metrics, the concept of left (right) fixed point of a mapping from a quasi-metric space to itself is proposed. Finally, two fixed point theorems in quasi-metric spaces are obtained.

We consider the monadic boundedness problem for least fixed points over FO formulae as a decision problem: Given a formula phi(X, x), positive in X, decide whether there is a uniform finite bound on the least fixed point recursion based on phi. Few fragments of FO are known to have a decidable boundedness problem; boundedness is known to be undecidable for many fragments. We here show that monadic boundedness is decidable for purely universal FO formulae without equality in which each non-recursive predicate occurs in just one polarity (e.g., only negatively). The restrictions are shown to be essential: waving either the polarity constraint or allowing positive occurrences of equality, the monadic boundedness problem for universal formulae becomes undecidable. The main result is based on a model theoretic analysis involving ideas from modal and guarded logics and a reduction to the monadic second-order theory of trees

Deterministic timed systems can be modeled as fixed point problems (B. Roscoe and G. Reed, 1988), (R. K. Yates, 1993), (E. A. Lee, 1999). In particular, any connected network of timed systems can be modeled as a single system with feedback, and the system behavior is the fixed point of the corresponding system equation, when it exists. For delta-causal systems, we can use the Cantor metric to measure the distance between signals and the Banach fixed-point theorem to prove the existence and uniqueness of a system behavior. Moreover, the Banach fixed-point theorem is constructive: it provides a method to construct the unique fixed point through iteration. In this paper, we extend this result to systems modeled with the superdense model of time (O. Maler et al., 1992), (Z. Manna and A. Pnueli, 1993) used in hybrid systems. We call the systems we consider eventually delta-causal, a strict generalization of delta-causal in which multiple events may be generated on a signal in zero time. With this model of time, we can use a generalized ultrametric (Generalized ultrametric spaces, I, 1996) instead of a metric to model the distance between signals. The existence and uniqueness of behaviors for such systems comes from the fixed-point theorem of (S. Priess-Crampe and P. Ribenboim, 1993), but this theorem gives no constructive method to compute the fixed point This leads us to define petrics, a generalization of metrics, which we use to generalize the Banach fixed-point theorem to provide a constructive fixed-point theorem. This new fixed-point theorem allows us to construct the unique behavior of eventually delta-causal systems.

A study is made of systems of Lipschitz-continuous mappings which are applied successively on an initial point x/sub 0/ in a closed nonempty complete metric space. All mappings possess the same fixed point x*, and are applied at random with repetitions by choosing a mapping from a finite set of such functions. A lower bound is found on the probability that the system's state after n iterations, x/sub n/, is within a rho -neighborhood of the common fixed point, x*. Conditions are developed that guarantee that the lower bound is (eventually) monotonically increasing in n. >

We consider the optimal robust disturbance attenuation problem (ORDAP) for continuous time-varying systems subject to time-varying unstructured uncertainty. We show that for causal (possibly time-varying) continuous systems, ORDAP is equivalent to finding the smallest fixed point of a "two-disk" type optimization problem under time-varying feedback control laws. Duality is applied in the context of nest algebra of causal stable systems, to prove existence of optimal continuous time-varying controllers. We also show that for time-invariant nominal plants, time-varying control laws offer no improvement over time-invariant feedback control laws and hence generalizing previous results obtained for discrete time-varying systems.

The finite wordlength effects in delta-operator formulated systems are analyzed and conditions for absence of nonzero equilibria in zero-input systems are provided. Also discussed are the options for their elimination. Considered are fixed, floating point as well as block floating point arithmetic with different quantization formats. It is shown that the problem is most likely to occur in fixed point systems. Although the problem is solvable within the fixed point arithmetic, block-floating point is a good alternative.

We give examples of classes of rigid structures which are of unbounded rigidity but least fixed point (Partial fixed point) logic can express all Boolean PTIME (PSPACE) queries on these classes. This shows that definability of linear order in FO+LEP although sufficient for it to capture Boolean PTIME queries, is not necessary even on the classes of rigid structures. The situation however appears very different for nonzero-ary queries. Next, we turn to the study of fixed point logics on arbitrary classes of structures. We completely characterize the recursively enumerable classes of finite structures on which PFP captures all PSPACE queries of arbitrary arities. We also state in some alternative forms several natural necessary and some sufficient conditions for PFP to capture PSPACE queries on classes of finite structures. The conditions similar to the ones proposed above work for LFP and PTIME also in some special cases but to prove the same necessary conditions in general for LFP to capture PTIME seems harder and remains open.

We recently introduced a class of highly nonlinear associative memories called morphological associative memories. We have previously shown that autoassociative morphological memories (AMMs) exhibit many desirable characteristics, including optimal absolute storage capacity and one-step convergence (G.X. Ritter et al., 1998). Other aspects of AMM performance still require more detailed analysis and/or improvement. The paper provides considerable insight into the functionality of AMMs by giving necessary and sufficient conditions for fixed points. We then show that the output generated upon presentation of an input pattern x is either the smallest fixed point /spl ges/x or the largest fixed point /spl les/x.