Ready to preorder: The case of weak process semantics

Recently, Aceto, Fokkink and Ingólfsdóttir proposed an algorithm to turn any sound and ground-complete axiomatisation of any preorder listed in the linear time-branching time spectrum at least as coarse as the ready simulation preorder, into a sound and ground-complete axiomatisation of the corresponding equivalence—its kernel. Moreover, if the former axiomatisation is ω-complete, so is the latter. Subsequently, de Frutos Escrig, Gregorio Rodríguez and Palomino generalised this result, so that the algorithm is applicable to any preorder at least as coarse as the ready simulation preorder, provided it is initials preserving. The current paper shows that the same algorithm applies equally well to weak semantics: the proviso of initials preserving can be replaced by other conditions, such as weak initials preserving and satisfying the second τ-law. This makes it applicable to all 87 preorders surveyed in “the linear time-branching time spectrum II” that are at least as coarse as the ready simulation preorder. We also extend the scope of the algorithm to infinite processes, by adding recursion constants. As an application of both extensions, we provide a ground-complete axiomatisation of the CSP failures equivalence for BCCS processes with divergence.     

Improving the efficiency index in enclosing a root of an equation

Recently several algorithms have been developed which achieve high efficiency index in enclosing a root of the equationf(x)=0 in an interval [a, b] over whichf(x) is continuous andf(a)f(b)<0. The highest efficiency index, 1.6686 ..., was achieved in [4] using the inverse cubic interpolation. This paper studies the possibility of improving efficiency index by using high order inverse interpolations. A class of algorithms are presented and the optimal one of the class has achieved the efficiency index 1.7282 ... With a user-given accurary ? and starting with the initial interval [a ₁,b ₁]=[a, b], these algorithms guarantee to find in finitely many iterations an enclosing interval [a _n ,b _n ] that contains a root of the equation and whose lengthb _n –a _n is smaller than ?. Numerical experiments indicate that the new algorithm performs very well in practice.     

(Bi)simulations up-to characterise process semantics

We define (bi)simulations up-to a preorder and show how we can use them to provide a coinductive, (bi)simulation-like, characterisation of semantic (equivalences) preorders for processes. In particular, we can apply our results to all the semantics in the linear time-branching time spectrum that are defined by preorders coarser than the ready simulation preorder.The relation between bisimulations up-to and simulations up-to allows us to find some new relations between the equivalences that define the semantics and the corresponding preorders. In particular, we have shown that the simulation up-to an equivalence relation is a canonical preorder whose kernel is the given equivalence relation. Since all of these canonical preorders are defined in an homogeneous way, we can prove properties for them in a generic way. As an illustrative example of this technique, we generate an axiomatic characterisation of each of these canonical preorders, that is obtained simply by adding a single axiom to the axiomatization of the original equivalence relation. Thus we provide an alternative axiomatization for any axiomatizable preorder in the linear time-branching time spectrum, whose correctness and completeness can be proved once and for all.Although we first prove, by induction, our results for finite processes, then we see, by using continuity arguments, that they are also valid for infinite (finitary) processes.     

Introducing reactive Kripke semantics and arc accessibility

Ordinary Kripke models are not reactive. When we evaluate (test/ measure) a formula A at a model m, the model does not react, respond or change while we evaluate. The model is static and unchanged. This paper studies Kripke models which react to the evaluation process and change themselves during the process. The additional device we add to Kripke semantics to make it reactive is to allow the accessibility relation to access itself. Thus the accessibility relation ${\cal R}$ of a reactive Kripke model contains not only pairs $(a, b) \in {\cal R}$ of possible worlds (b is accessible to a, i.e., there is an accessibility arc from a to b) but also pairs of the form $(t, (a, b))\in {\cal R}$ , meaning that the arc (a,b) is accessible to t, or even connections of the form $((a,b), (c,d))\in {\cal R}$ . This new kind of Kripke semantics allows us to characterise more axiomatic modal logics (with one modality $\square$ ) by a class of reactive frames. There are logics which cannot be characterised by ordinary frames but which can be characterised by reactive frames. We also discuss the manifestation of the ??reactive?? idea in the context of automata theory, where we allow the automaton to react and change it??s own definition as it responds to input, and in graph theory, where the graph can change under us as we manipulate it.     

Discrete Semantics for Hybrid Automata

Many natural systems exhibit a hybrid behavior characterized by a set of continuous laws which are switched by discrete events. Such behaviors can be described in a very natural way by a class of automata called hybrid automata. Their evolution are represented by both dynamical systems on dense domains and discrete transitions. Once a real system is modeled in a such framework, one may want to analyze it by applying automatic techniques, such as Model Checking or Abstract Interpretation. Unfortunately, the discrete/continuous evolutions not only provide hybrid automata of great flexibility, but they are also at the root of many undecidability phenomena. This paper addresses issues regarding the decidability of the reachability problem for hybrid automata (i.e., “can the system reach a state a from a state b?”) by proposing an “inaccurate” semantics. In particular, after observing that dense sets are often abstractions of real world domains, we suggest, especially in the context of biological simulation, to avoid the ability of distinguishing between values whose distance is less than a fixed ε. On the ground of the above considerations, we propose a new semantics for first-order formulæ which guarantees the decidability of reachability. We conclude providing a paradigmatic biological example showing that the new semantics mimics the real world behavior better than the precise one.     

Concurrent testing of processes

Using a form of ST-operational semantics we develop a noninterleaving semantic theory of processes based on testing. This operational semantics is based on the assumption that all actions have a non-zero duration and the allowed tests can therefore distinguish between the beginning and the termination of actions. The result is a semantic theory in which concurrency is differentiated from nondeterminism.We show that the semantic preorder based on these tests is preserved by so-called stable action refinements and may be characterised as the largest such preorder contained in the standard testing preorder.This work has been supported by the ESPRIT/BRA CEDISYS project and the ESPRC project HI6357     

Darboux transformations for factorable Laplace operators

Factorable Laplace operators of the form L = ? _x ? _y + a? _x + b? _y + c, where the coefficients a, b, c are not necessarily constants, are considered. For these operators, the Darboux transformations \(L\xrightarrow{M}L_1\) , M ∈ K[? _x ], defined by the intertwining relation NL = L ₁ M are considered. It is shown that only the following cases are possible: either (1) M ∩ ker? _x + b = {0} and L ₁ is also factorable or (2) M ∩ ker? _x + b contains a nonzero element. We prove that, in both cases, the Darboux transformation can be represented as a product of first-order Darboux transformations. For case (2), the proof is based on the fact that the Darboux transformation of operator L can be reduced to Darboux transformations of first-order operators.     

CPO Models for Compact GSOS Languages

In this paper, we present a general way of giving denotational semantics to a class of languages equipped with an operational semantics that fits the GSOS format of Bloom, Istrail, and Meyer. The canonical model used for this purpose will be Abramsky's domain of synchronization trees, and the denotational semantics automatically generated by our methods will be guaranteed to be fully abstract with respect to the finitely observable part of the bisimulation preorder. In the process of establishing the full abstraction result, we also obtain several general results on the bisimulation preorder (including a complete axiomatization for it), and give a novel operational interpretation of GSOS languages.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

Stability of properties of Kolmogorov complexity under relativization

Assume that a tuple of binary strings \(\bar a\) = 〈a ₁ ..., a _n 〉 has negligible mutual information with another string b. Does this mean that properties of the Kolmogorov complexity of \(\bar a\) do not change significantly if we relativize them to b? This question becomes very nontrivial when we try to formalize it. In this paper we investigate this problem for a special class of properties (for properties that can be expressed by an ?-formula). In particular, we show that a random (conditional on \(\bar a\)) oracle b does not help to extract common information from the strings a _i .     

Testing Preorders for Probabilistic Processes

We present a testing preorder for probabilistic processes based on a quantification of the probability with which processes pass tests. The theory enjoys close connections with the classical testing theory of De Nicola and Hennessy in that whenever a process passes a test with probability 1 (respectively some nonzero probability) in our setting, then the process must (respectively may) pass the test in the classical theory. We also develop an alternative characterization of the probabilistic testing preorders that takes the form of a mapping from probabilistic traces to the interval [0, 1], where a probabilistic trace is an alternating sequence of actions and probability distributions over actions. Finally, we give proof techniques, derived from the alternative characterizations, for establishing preorder relationships between probabilistic processes. The utility of these techniques is demonstrated by means of some simple examples.     

When are Two Numerical Polynomials Relatively Prime?

Let a and b be two polynomials having numerical coefficients. We consider the question: When are a and b relatively prime? Since the coefficients of a and b are approximant, the question is the same as: When are two polynomials relatively prime, even after small perturbations of the coefficients?In this paper we provide a numeric parameter for determining whether two polynomials are prime, even under small perturbations of the coefficients. Our methods rely on an inversion formula for Sylvester matrices to establish an effective criterion for relative primeness. The inversion formula can also be used to approximate the condition number of a Sylvester matrix.     

Inequalities for the Number of Walks in Graphs

We investigate the growth of the number w _k of walks of length k in undirected graphs as well as related inequalities. In the first part, we deduce the inequality w _2a+c ?w _2(a+b)+c ≤w _2a ?w _2(a+b+c), which we call the Sandwich Theorem. It unifies and generalizes an inequality by Lagarias et al. and an inequality by Dress and Gutman. In the same way, we derive the inequality w _2a+c (v,v)?w _2(a+b)+c (v,v)≤w _2a (v,v)?w _2(a+b+c)(v,v) for the number w _k (v,v) of closed walks of length k starting at a given vertex v. We then use a theorem of Blakley and Dixon to show $w_{2\ell+p}^{k}\leq w_{2\ell+pk}\cdot w_{2\ell}^{k-1}$ , which unifies and generalizes an inequality by Erd?s and Simonovits and, again, the inequality by Dress and Gutman. Both results can be translated directly into the corresponding forms using the higher order densities, which extends former results. In the second part, we provide a new family of lower bounds for the largest eigenvalue λ ₁ of the adjacency matrix based on closed walks. We apply the Sandwich Theorem to show monotonicity in this and a related family of lower bounds of Nikiforov. This leads to generalized upper bounds for the energy of graphs. In the third part, we demonstrate that a further natural generalization of the Sandwich Theorem is not valid for general graphs. We show that the inequality w _a+b ?w _a+b+c ≤w _a ?w _a+2b+c does not hold even in very restricted cases like w ₁?w ₂≤w ₀?w ₃ (i.e., $\bar{d}\cdot w_{2}\leq w_{3}$ ) in the context of bipartite or cycle free graphs. In contrast, we show that surprisingly this inequality is always satisfied for trees and we show how to construct worst-case instances (regarding the difference of both sides of the inequality) for a given degree sequence. We also prove the inequality w ₁?w ₄≤w ₀?w ₅ (i.e., $\bar{d}\cdot w_{4}\leq w_{5}$ ) for trees and conclude with a corresponding conjecture for longer walks.     

A neural network based on the generalized Fischer-Burmeister function for nonlinear complementarity problems

In this paper, we consider a neural network model for solving the nonlinear complementarity problem (NCP). The neural network is derived from an equivalent unconstrained minimization reformulation of the NCP, which is based on the generalized Fischer-Burmeister function ?_p(a,b)=‖(a,b)‖_p-(a+b). We establish the existence and the convergence of the trajectory of the neural network, and study its Lyapunov stability, asymptotic stability as well as exponential stability. It was found that a larger p leads to a better convergence rate of the trajectory. Numerical simulations verify the obtained theoretical results.     

Secure multiplication of shared secrets in the exponent

We present a new protocol for the following task. Given two secrets a,b shared among n players, compute the value gab.The protocol uses the generic BGW approach for multiplication of shared secrets, but we show that if one is computing “multiplications in the exponent” the polynomial randomization step can be avoided (assuming the Decisional Diffie-Hellman Assumption holds). This results in a non-interactive and more efficient protocol.     

Simulated annealing type algorithms for multivariate optimization

We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX _k +1 =X _k ?a _k (▽U(X _k ) + ξ_k) +b _k W _k . HereU(·) is a smooth function on a compact subset of ? ^d , {ξ_k} is a sequence of ? ^d -valued random variables, {W _k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a _k }, {b _k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), {ξ _k }, {a _k }, and {b _k } thatX _k converges in probability to the set of global minima ofU(·). A careful treatment of howX _k is restricted to a compact set and its effect on convergence is given.     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.