Author name cluster

Abbas Edalat

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

1 author row

TCS Journal 2023 Journal Article

Recursive solution of initial value problems with temporal discretization

Abbas Edalat
Amin Farjudian
Yiran Li

We construct a continuous domain, as a model of interval analysis, for temporal discretization of differential equations. By using this domain, and the domain of Lipschitz maps, we formulate a generalization of the Euler operator, which exhibits second-order convergence. We prove computability of the operator within the framework of effectively given domains. The operator only requires the vector field of the differential equation to be Lipschitz continuous, in contrast to the related operators in the literature which require the vector field to be at least continuously differentiable. Within the same framework, we also analyze temporal discretization and computability of another variant of the Euler operator formulated according to Runge-Kutta theory. We prove that, compared with this variant, the second-order operator that we formulate directly, not only imposes weaker assumptions on the vector field, but also exhibits superior convergence rate. We implement the first-order, second-order, and Runge-Kutta Euler operators using arbitrary-precision interval arithmetic, and report on some experiments. The experiments confirm our theoretical results. In particular, we observe the superior convergence rate of our second-order operator compared with the Runge-Kutta Euler and the common (first-order) Euler operators.

Details DOI

TCS Journal 2017 Journal Article

A domain-theoretic approach to Brownian motion and general continuous stochastic processes

Paul Bilokon
Abbas Edalat

We introduce a domain-theoretic framework for continuous-time, continuous-state stochastic processes. The laws of stochastic processes are embedded into the space of maximal elements of the normalised probabilistic power domain on the space of continuous interval-valued functions endowed with the relative Scott topology. We use the resulting ω-continuous bounded complete dcpo to obtain partially defined stochastic processes and characterise their computability. For a given continuous stochastic process, we show how its domain-theoretic, i. e. , finitary, approximations can be constructed, whose least upper bound is the law of the stochastic process. As a main result, we apply our methodology to Brownian motion. We construct a partially defined Wiener measure and show that the Wiener measure is computable within the domain-theoretic framework.

Details DOI

TCS Journal 2015 Journal Article

A derivative for complex Lipschitz maps with generalised Cauchy–Riemann equations

Abbas Edalat

We introduce the Lipschitz derivative or the L-derivative of a locally Lipschitz complex map: it is a Scott continuous, compact and convex set-valued map that extends the classical derivative to the bigger class of locally Lipschitz maps and allows an extension of the fundamental theorem of calculus and a new generalisation of Cauchy–Riemann equations to these maps, which form a continuous Scott domain. We show that a complex Lipschitz map is analytic in an open set if and only if its L-derivative is a singleton at all points in the open set. The calculus of the L-derivative for sum, product and composition of maps is derived. The notion of contour integration is extended to Scott continuous, non-empty compact, convex valued functions on the complex plane, and by using the L-derivative, the fundamental theorem of contour integration is extended to these functions.

Details DOI

I&C Journal 2013 Journal Article

A computational model for multi-variable differential calculus

Abbas Edalat
André Lieutier
Dirk Pattinson

We develop a domain-theoretic computational model for multi-variable differential calculus, which for the first time gives rise to data types for piecewise differentiable or more generally Lipschitz functions, by constructing an effectively given continuous Scott domain for real-valued Lipschitz functions on finite dimensional Euclidean spaces. The model for real-valued Lipschitz functions of n variables is built as a sub-domain of the product of two domains by tupling together consistent information about locally Lipschitz functions and their differential properties as given by their L-derivative or equivalently Clarke gradient, which has values given by non-empty, convex and compact subsets of R n. To obtain a computationally practical framework, the derivative information is approximated by the best fit compact hyper-rectangles in R n. In this case, we show that consistency of the function and derivative information can be decided by reducing it to a linear programming problem. This provides an algorithm to check consistency on the rational basis elements of the domain, implying that the domain can be equipped with an effective structure and giving a computable framework for multi-variable differential calculus. We also develop a domain-theoretic, interval-valued, notion of line integral and show that if a Scott continuous function, representing a non-empty, convex and compact valued vector field, is integrable, then its interval-valued integral over any closed piecewise C 1 path contains zero. In the case that the derivative information is given in terms of compact hyper-rectangles, we use techniques from the theory of minimal surfaces to deduce the converse result: a hyper-rectangular valued vector field is integrable if its interval-valued line integral over any piecewise C 1 path contains zero. This gives a domain-theoretic extension of the fundamental theorem of path integration. Finally, we construct the least and the greatest piecewise linear functions obtained from a pair of function and hyper-rectangular derivative information. When the pair is consistent, this provides the least and greatest maps to witness consistency.

Details DOI

NeurIPS Conference 2013 Conference Paper

Capacity of strong attractor patterns to model behavioural and cognitive prototypes

Abbas Edalat

We solve the mean field equations for a stochastic Hopfield network with temperature (noise) in the presence of strong, i. e. , multiply stored patterns, and use this solution to obtain the storage capacity of such a network. Our result provides for the first time a rigorous solution of the mean field equations for the standard Hopfield model and is in contrast to the mathematically unjustifiable replica technique that has been hitherto used for this derivation. We show that the critical temperature for stability of a strong pattern is equal to its degree or multiplicity, when sum of the cubes of degrees of all stored patterns is negligible compared to the network size. In the case of a single strong pattern in the presence of simple patterns, when the ratio of the number of all stored patterns and the network size is a positive constant, we obtain the distribution of the overlaps of the patterns with the mean field and deduce that the storage capacity for retrieving a strong pattern exceeds that for retrieving a simple pattern by a multiplicative factor equal to the square of the degree of the strong pattern. This square law property provides justification for using strong patterns to model attachment types and behavioural prototypes in psychology and psychotherapy.

PDF Details

I&C Journal 2009 Journal Article

A computable approach to measure and integration theory

Abbas Edalat

We introduce a computable framework for Lebesgue’s measure and integration theory in the spirit of domain theory. For an effectively given second countable locally compact Hausdorff space and an effectively given finite Borel measure on the space, we define a recursive measurable set, which extends the corresponding notion due to S˜anin for the Lebesgue measure on the real line. We also introduce the stronger notion of a computable measurable set, where a measurable set is approximated from inside and outside by sequences of closed and open subsets, respectively. The more refined property of computable measurable sets give rise to the idea of partial measurable subsets, which naturally form a domain for measurable subsets. We then introduce interval-valued measurable functions and develop the notion of recursive and computable measurable functions using interval-valued simple functions. This leads us to the interval versions of the main results in classical measure theory. The Lebesgue integral is shown to be a continuous operator on the domain of interval-valued measurable functions and the interval-valued Lebesgue integral provides a computable framework for integration.

Details DOI

I&C Journal 2002 Journal Article

Bisimulation for Labelled Markov Processes

Josée Desharnais
Abbas Edalat
Prakash Panangaden

In this paper we introduce a new class of labelled transition systems—labelled Markov processes— and define bisimulation for them. Labelled Markov processes are probabilistic labelled transition systems where the state space is not necessarily discrete. We assume that the state space is a certain type of common metric space called an analytic space. We show that our definition of probabilistic bisimulation generalizes the Larsen–Skou definition given for discrete systems. The formalism and mathematics is substantially different from the usual treatment of probabilistic process algebra. The main technical contribution of the paper is a logical characterization of probabilistic bisimulation. This study revealed some unexpected results, even for discrete probabilistic systems. • Bisimulation can be characterized by a very weak modal logic. The most striking feature is that one has no negation or any kind of negative proposition. • We do not need any finite branching assumption, yet there is no need of infinitary conjunction. We also show how to construct the maximal autobisimulation on a system. In the finite state case, this is just a state minimization construction. The proofs that we give are of an entirely different character than the typical proofs of these results. They use quite subtle facts about analytic spaces and appear, at first sight, to be entirely nonconstructive. Yet one can give an algorithm for deciding bisimilarity of finite state systems which constructs a formula that witnesses the failure of bisimulation.

Details DOI

TCS Journal 2002 Journal Article

Foundation of a computable solid modelling

Abbas Edalat
André Lieutier

Solid modelling and computational geometry are based on classical topology and geometry in which the basic predicates and operations, such as membership, subset inclusion, union and intersection, are not continuous and therefore not computable. But a sound computational framework for solids and geometry can only be built in a framework with computable predicates and operations. In practice, correctness of algorithms in computational geometry is usually proved using the unrealistic Real RAM machine model of computation, which allows comparison of real numbers, with the undesirable result that correct algorithms, when implemented, turn into unreliable programs. Here, we use a domain-theoretic approach to recursive analysis to develop the basis of an effective and realistic framework for solid modelling. This framework is equipped with a well defined and realistic notion of computability which reflects the observable properties of real solids. The basic predicates and operations on solids are computable in this model which admits regular and non-regular sets and supports a design methodology for actual robust algorithms. Moreover, the model is able to capture the uncertainties of input data in actual CAD situations.

Details DOI

I&C Journal 2000 Journal Article

Integration in Real PCF

Abbas Edalat
Martı́n Hötzel Escardó

Real PCF is an extension of the programming language PCF with a data type for real numbers. Although a Real PCF definable real number cannot be computed in finitely many steps, it is possible to compute an arbitrarily small rational interval containing the real number in a sufficiently large number of steps. Based on a domain-theoretic approach to integration, we propose two approaches to integration in Real PCF. One consists in adding integration as primitive. The other consists in adding a primitive for function maximization and then recursively defining integration from maximization. In both cases we have a computational adequacy theorem for the corresponding extension of Real PCF. Moreover, based on previous work on Real PCF definability, we show that Real PCF extended with the maximization operator is universal.

Details DOI

TCS Journal 1999 Journal Article

A domain-theoretic approach to computability on the real line

Abbas Edalat
Philipp Sünderhauf

In recent years, there has been a considerable amount of work on using continuous domains in real analysis. Most notably are the development of the generalized Riemann integral with applications in fractal geometry, several extensions of the programming language PCF with a real number data type, and a framework and an implementation of a package for exact real number arithmetic. Based on recursion theory we present here a precise and direct formulation of effective representation of real numbers by continuous domains, which is equivalent to the representation of real numbers by algebraic domains as in the work of Stoltenberg-Hansen and Tucker. We use basic ingredients of an effective theory of continuous domains to spell out notions of computability for the reals and for functions on the real line. We prove directly that our approach is equivalent to the established Turing-machine based approach which dates back to Grzegorczyk and Lacombe, is used by Pour-El & Richards in their foundational work on computable analysis, and, moreover, is the standard notion of computability among physicists as in the work of Penrose. Our framework makes it possible to capture partial functions in an elegant way and it extends to the complex numbers and the n-dimensional Euclidean space.

Details DOI

TCS Journal 1999 Journal Article

Computable Banach spaces via domain theory

Abbas Edalat
Philipp Sünderhauf

This paper extends the order-theoretic approach to computable analysis via continuous domains to complete metric spaces and Banach spaces. We employ the domain of formal balls to define a computability theory for complete metric spaces. For Banach spaces, the domain specialises to the domain of closed balls, ordered by reversed inclusion. We characterise computable linear operators as those which map computable sequences to computable sequences and are effectively bounded. We show that the domain-theoretic computability theory is equivalent to the well-established approach by Pour-El and Richards.

Details DOI

TCS Journal 1998 Journal Article

A computational model for metric spaces

Abbas Edalat
Reinhold Heckmann

For every metric space X, we define a continuous poset BX such that X is homeomorphic to the set of maximal elements of BX with the relative Scott topology. The poset BX is a dcpo iff X is complete, and ω-continuous iff X is separable. The computational model BX is used to give domain-theoretic proofs of Banach's fixed point theorem and of two classical results of Hutchinson: on a complete metric space, every hyperbolic iterated function system has a unique non-empty compact attractor, and every iterated function system with probabilities has a unique invariant measure with bounded support. We also show that the probabilistic power domain of BX provides an ω-continuous computational model for measure theory on a separable complete metric space X.

Details DOI

I&C Journal 1996 Journal Article

Power Domains and Iterated Function Systems

Abbas Edalat

We introduce the notion of weakly hyperbolic iterated function system (IFS) on a compact metric space, which generalises that of hyperbolic IFS. Based on a domain-theoretic model, which uses the Plotkin power domain and the probabilistic power domain respectively, we prove the existence and uniqueness of the attractor of a weakly hyperbolic IFS and the invariant measure of a weakly hyperbolic IFS with probabilities, extending the classic results of Hutchinson for hyperbolic IFSs in this more general setting. We also present finite algorithms to obtain discrete and digitised approximations to the attractor and the invariant measure, extending the corresponding algorithms for hyperbolic IFSs. We then prove the existence and uniqueness of the invariant distribution of a weakly hyperbolic recurrent IFS and obtain an algorithm to generate the invariant distribution on the digitised screen. The generalised Riemann integral is used to provide a formula for the expected value of almost everywhere continuous functions with respect to this distribution. For hyperbolic recurrent IFSs and Lipschitz maps, one can estimate the integral up to any threshold of accuracy.

Details DOI

TCS Journal 1995 Journal Article

Domain theory and integration

Abbas Edalat

We present a domain-theoretic framework for measure theory and integration of bounded real-valued functions with respect to bounded Borel measures on compact metric spaces. The set of normalised Borel measures of the metric space can be embedded into the maximal elements of the normalised probabilistic power domain of its upper space. Any bounded Borel measure on the compact metric space can then be obtained as the least upper bound of an ω-chain of linear combinations of point valuations (simple valuations) on the upper space, thus providing a constructive framework for these measures. We use this setting to define a new notion of integral of a bounded real-valued function with respect to a bounded Borel measure on a compact metric space. By using an ω-chain of simple valuations, whose lub is the given Borel measure, we can then obtain increasingly better approximations to the value of the integral, similar to the way the Riemann integral is obtained in calculus by using step functions. We show that all the basic results in the theory of Riemann integration can be extended in this more general setting. Furthermore, with this new notion of integration, the value of the integral, when it exists, coincides with the Lebesgue integral of the function. An immediate area for application is in the theory of iterated function systems with probabilities on compact metric spaces, where we obtain a simple approximating sequence for the integral of a real-valued almost everywhere continuous function with respect to the invariant measure.

Details DOI

TCS Journal 1993 Journal Article

I-Categories as a framework for solving domain equations

Abbas Edalat
Michael B. Smyth

An abstract notion of category of information systems or I-category is introduced as a generalisation of Scott's well-known category of information systems. As in the theory of partial orders, I-categories can be complete or ω-algebraic, and it is shown that ω-algebraic I-categories can be obtained from a certain completion of countable I-categories. The proposed axioms for a complete I-category introduce a global partial order on the morphisms of the category, making them a cpo. An initial algebra theorem for a class of functors continuous on the cpo of morphisms is proved, thus giving canonical solution of domain equations; an effective version of these results for ω-algebraic I-categories is also provided. Some basic examples of I-categories representing the categories of sets, Boolean algebras, Scott domains and continuous Scott domains are constructed.

Details DOI