Embedding Markov normal algorithms within the λ-calculus

Most attempts to explain some aspect of computation formally have relied on a single formalism. This paper presents examples of a blending of two well-known formalisms, the ,λ-calculus and Markov normal algorithms, and illustrates the additional expressive power of the combined formalism.     

On the definition of stochastic λ-transducers

We propose a formal definition for the general notion of stochastic transducer, called stochastic λ-transducer. Our definition is designed with two objectives in mind: (i) to extend naturally the established notion of stochastic automaton with output—as defined in the classic books of [A. Paz, Introduction to Probabilistic Automata, Academic Press, New York and London, 1971; P. Starke, Abstract Automata, North-Holland, Academic Press, 1972.]—by permitting pairs of input-output words of different lengths; (ii) to be compatible with the more general notion of weighted transducer so that one can apply tools of weighted transducers to address certain computational problems involving stochastic transducers. The new transducers can be used to model stochastic input-output processes that cannot be modelled using classical stochastic automata with output.     

Loop headers in λ-calculus or CPS

The introduction of a loop header block facilitates the hoisting of loop-invariant code from a loop. In a -calculus intermediate representation, which has a notion of scope, this transformation is particularly useful. Loop headers with scope also solve a problem with in-line expansion of recursive functions or loops: if done naively, only the first iteration is inlined. A loop header can encapsulate the loop or recursion for better in-line expansion. This optimization improves performance by about 5% in Standard ML of New Jersey.     

On the class of λ-statistically convergent difference sequences of fuzzy numbers

In this study, we introduce the sets $\left[ V,\lambda ,p\right] _{\Updelta }^{{\mathcal{F}}},\left[ C,1,p\right] _{\Updelta }^{{\mathcal{F}}}$ and examine their relations with the classes of $ S_{\lambda }\left( \Updelta ,{\mathcal{F}}\right)$ and $ S_{\mu }\left( \Updelta ,{\mathcal{F}}\right)$ of sequences for the sequences $\left( \lambda _{n}\right)$ and $\left( \mu _{n}\right) , 0<p<\infty $ and difference sequences of fuzzy numbers.     

Automatic binding time analysis for a typed λ-calculus

A binding time analysis imposes a distinction between the computations to be performed early (e.g. at compile-time) and those to be performed late (e.g. at run-time). For the λ-calculus this distinction is formalized by a two-level λ-calculus. We present an algorithm for static analysis of the binding times of a typed λ-calculus with products, sums, lists and general recursive types. Given partial information about the binding times of some of the subexpressions it will complete that information such that (i) early bindings may be turned into late bindings but not vice versa, (ii) the resulting two-level λ-expression reflects our intuition about binding times, e.g. that early bindings are performed before late bindings, and (iii) as few changes as possible have been made compared with the initial binding information. The results can be applied in the implementation of functional languages and in semantics directed compiling.     

On the combination of logical and probabilistic models for?information analysis

Formal logical tools are able to provide some amount of reasoning support for information analysis, but are unable to represent uncertainty. Bayesian network tools represent probabilistic and causal information, but in the worst case scale as poorly as some formal logical systems and require specialized expertise to use effectively. We describe a framework for systems that incorporate the advantages of both Bayesian and logical systems. We define a formalism for the conversion of automatically generated natural deduction proof trees into Bayesian networks. We then demonstrate that the merging of such networks with domain-specific causal models forms a consistent Bayesian network with correct values for the formulas derived in the proof. In particular, we show that hard evidential updates in which the premises of a proof are found to be true force the conclusions of the proof to be true with probability one, regardless of any dependencies and prior probability values assumed for the causal model. We provide several examples that demonstrate the generality of the natural deduction system by using inference schemes not supportable directly in Horn clause logic. We compare our approach to other ones, including some that use non-standard logics.     

The completeness and applications of the formal system B

Since the formal deductive system (?) was built up in 1997, it has played important roles in the theoretical and applied research of fuzzy logic and fuzzy reasoning. But, up to now, the completeness problem of the system (?) is still an open problem. In this paper, the properties and structure of R0 algebras are further studied, and it is shown that every tautology on the R0 interval [0,1] is also a tautology on any R0 algebra. Furthermore, based on the particular structure of (?) -Lindenbaum algebra, the completeness and strong completeness of the system (?) are proved. Some applications of the system (?) in fuzzy reasoning are also discussed, and the obtained results and examples show that the system (?) is suprior to some other important fuzzy logic systems.     

On the algebraic specification of infinite objects — ordered and continuous models of algebraic types

Summary The concept of algebraic types is adapted to allow axiomatic characterizations of ordered and continuous algebras; infinite objects are then limit points in the carriers of certain continuous algebras. We mainly study implicative types, i.e., types the axioms of which are conditional inequations describing partial orders. The isomorphism classes of termgenerated ordered models of an implicative type are shown to form a complete lattice under the homomorphism ordering; this includes the wellknown initiality results for equational and conditional types as special cases. For types whose axioms specify strictness of the operations, the initial models are shown to correspond to flat domains.As a special kind of continuous algebras we consider inductively generated algebras, viz. the ideal completions of term-generated ordered algebras. For an inequational type, i.e., an implicative type where all axiom premises are empty, the completion of models always yields models again, whereas for implicative types this holds only in restricted cases. One such case is provided by hierarchic types which are complete and consistent relative to their primitive parts, and which satisfy certain conditions about limit points.Examples of algebras that can be specified by such types include those of finite and infinite streams, of sets of atoms under the Egli-Milner ordering, Milner's synchronisation trees, and that of a simple functional language over the natural numbers.This research was carried out within the Sonderforschungsbereich 49 Programmiertechnik, Munich, Federal Republic of Germany     

On probabilistic models for estimating the coordinates of the object’s position in a topology of one-dimensional manifolds

The probabilistic models underlying the estimation of the coordinates of an object’s position in a topology of one-dimensional manifolds are analysed in the case of a multiangle measuring system. The specific features of these models are identified, and the sequence of their use in processing data produced by a three-angle measuring system is described.     

Occurrence Counting Analysis for the π-calculus

We propose an abstract interpretation-based analysis for automatically proving non-trivial properties of mobile systems of processes. We focus on properties relying on the number of occurrences of processes during computation sequences, such as mutual exclusion and non-exhaustion of resources.We design a non-standard semantics for the π-calculus in order to explicitly trace the origin of channels and to solve efficiently problems set by α-conversion and non-deterministic choices. We abstract this semantics into an approximate one. The use of a relational domain for counting the occurrences of processes allows us to prove quickly and efficiently properties such as mutual exclusion and non-exhaustion of resources. At last, dynamic partitioning allows us to detect some configurations by which no infinite computation sequences can pass.     

Accelerating the Computation of PageRank by λ2 Extrapolation

In order to improve the running performance of standard PageRank algorithm, a new extrapolation algorithm is proposed, which exploits the second eigenvalue λ2 of web page hyperlink probabilistic matrix. Experiments indicate that the new algorithm with , λ2-extrapolation can significantly outperform the standard PageRank. Compared with the standard PageRank algorithm, both the number of iterations up to the desired tolerances and the clock time used by computing importance scores of pages in the new algorithm are reduced effectively.     

On the bounds of the trajectories of differential systems†

The behaviour of differential systems is investigated by considering the stability and instability of such systems with respect to certain sub-sets of the state space These Sets may in general be time-varying, and their properties do not only yield information about the stability of a system but also estimates of the bounds of the system trajectories. In all cases the results which are established yield sufficient conditions for stability and instability, and in general involve the existence of Lyapunov-like functions which do not appear to possess the usual definiteness requirements on V and [Vdot].

The developed theory is applied to two special cases: in one case, only time-invariant sub-sets are considered: in the second case, the time interval [t₀, ∞) over which the systems me defined is truncated to [t ₀, t _a  + T), T < ∞, So the that case of stability over a finite time interval may be considered.     

How do I update my model? On the resilience of Predictive Process Monitoring models to change

Knowledge and Information Systems - Existing well-investigated Predictive Process Monitoring techniques typically construct a predictive model based on past process executions and then use this...     

On the sensitivity of the linear state regulator†

The sensitivity of the optimal response of a linear system with quadratic performance index to changes in the weighting factors in the performance index is determined. This necessitates finding the sensitivity of the feedback gain matrix K to changes in the weighting factors. It is shown that the sensitivities of K can be obtained as the solution of a set of linear matrix differential equations. Further, for time-invariant systems and an infinite time interval, it is seen that the sensitivities of K are found more simply by solving a set of linear algebraic matrix equations.     

On the stability of interconnected systems†

This paper investigates the stability of systems which can be regarded as composed of interconnected subsystems. A sufficient condition for inputs-output L ^p stability, in terms of the L ^p gains of the subsystems and their interconnections is derived. For the case of L ² stability, it is compared with other criteria for asymptotic stability, obtained by Lyapunov techniques, and shown to give better results for a certain class of systems.     

On the cost–effectiveness of PRAMs

We introduce a formalism which allows to treat computer architecture as a formal optimization problem. We apply this to the design of shared memory parallel machines. While present parallel computers of this type only support the programming model of a shared memory but often process simultaneous access by several processors to the shared memory sequentially, theoretical computer science offers solutions for this problem that are provably fast and asymptotically optimal. But the constants in these constructions seemed to be too large to let them be competitive. We modify these constructions under engineering aspects and improve the price/performance ratio by roughly a factor of 6. The resulting machine has surprisingly good price/performance ratio even if compared with distributed memory machines. For almost all access patterns of all processors into the shared memory, access is as fast as the access of only a single processor. Received: 29 June 1993 / 22 June 1999     

On the α-migrativity of multivariate semi-copulas

In this paper we introduce and study the α-migrative property for the class of multivariate semi-copulas. In particular, a characterization of α-migrative copulas is provided.