Trace Machines for Observing Continuous-Time Markov Chains

In this paper, we study several linear-time equivalences (Markovian trace equivalence, failure and ready trace equivalence) for continuous-time Markov chains that refer to the probabilities for timed execution paths. Our focus is on testing scenarios by means of push-button experiments with appropriate trace machines and a discussion of the connections between the equivalences. For Markovian trace equivalence, we provide alternative characterizations, including one that abstracts away from the time instances where actions are observed, but just reports on the average sojourn times in the states. This result is used for a reduction of the question whether two finite-state continuous-time Markov chains are Markovian trace equivalent to the probabilistic trace equivalence problem for discrete-time Markov chains (and the latter is known to be solvable in polynomial time).     

On Deciding Readiness and Failure Equivalences for Processes

In this paper, we study the complexity of deciding readiness and failure equivalences for finite state processes and recursively defined processes specified by normed context-free grammars (CFGs) in Greibach normal form (GNF). The results are as follows: (1) Readiness and failure equivalences for processes specified by normed GNF CFGs are both undecidable. For this class of processes, the regularity problem with respect to failure or readiness equivalence is also undecidable. Moreover, all these undecidability results hold even for locally unary processes. In the unary case, these problems become decidable. In fact, they are Π^p₂-complete, We also show that with respect to bisimulation equivalence, the regularity for processes specified by normed GNF CFGs is NL-complete. (2) Readiness and failure equivalences for finite state processes are PSPACE-complete. This holds even for locally unary finite state processes. These two equivalences are co-NP-complete for unary finite state processes. Further, for acyclic finite state processes, readiness and failure equivalences are co-NP-complete and they are NL-complete in the unary case. (3) For finite tree processes, we show that finite trace, readiness, and failure equivalences are all L-complete. Further, the results remain true for the unary case. Our results provide a complete characterization of the computational complexity of deciding readiness and failure equivalences for several important classes of processes.     

Rewriting with Equivalence Relations in ACL2

Traditionally, a conditional rewrite rule directs replacement of one term by another term that is provably equal to it, perhaps under some hypotheses. This paper generalizes the notion of rewrite rule to permit the connecting relation to be merely an equivalence relation. We then extend the algorithm for applying rewrite rules. Applications of these generalized rewrite rules are only admissible in certain equivalential contexts, so the algorithm tracks which equivalence relations are to be preserved and admissible generalized rewrite rules are selected according to this context. We introduce the notions of congruence rule and refinement rule. We also introduce the idea of generated equivalences, corresponding to a new equivalence relation generated by a set of pre-existing ones. Generated equivalences are used to give the rewriter broad access to admissible generalized rewrite rules. We discuss the implementation of these notions in the ACL2 theorem prover. However, the discussion does not assume familiarity with ACL2, and these ideas can be applied to other reasoning systems as well.     

Complete inference systems for weak bisimulation equivalences in the π-calculus

Proof systems for weak bisimulation equivalences in the π-calculus are presented, and their soundness and completeness are shown. Two versions of π-calculus are investigated, one without and the other with the mismatch operator. For each version of the calculus proof systems for both late and early weak bisimulation equivalences are studied. Thus there are four proof systems in all. These inference systems are related in a natural way: the inference system for early equivalence is obtained from the one for late equivalence by replacing the inference rule for input prefix, while the inference system for the version of π-calculus with mismatch is obtained by adding a single inference rule for mismatch to the one for the version without it. The proofs of the completeness results rely on the notion of symbolic bisimulation.     

An Algorithm for Finding the Causal Distributed Breakpoint

Acausal distributed breakpointis one of the fundamental mechanisms for debugging distributed programs. It is initiated by a sequential breakpoint in one process of a distributed computation, and restores each process to theearlieststate that reflects all events that happened causally before the sequential breakpoint. This paper presents an algorithm for finding the causal distributed breakpoint when a sequential breakpoint occurs. To find the causal distributed breakpoint efficiently, some information about dependency of events is piggybacked in every message and is logged at each process. The algorithm requiresO(1) information in each message and finds the causal distributed breakpoint inO(nlogn+m) time, wherendenotes the number of processes andmdenotes the number of distinct pairs of processes directly communicating with each other.     

Itineraries of rigid rotations and diffeomorphisms of the circle

We examine the itinerary of 0∈S¹=R/Z under the rotation by α∈R?Q. The motivating question is: if we are given only the itinerary of 0 relative to I⊂S¹, a finite union of closed intervals, can we recover α and I? We prove that the itineraries do determine α and I up to certain equivalences. Then we present elementary methods for finding α and I. Moreover, if g:S¹→S¹ is a C², orientation preserving diffeomorphism with an irrational rotation number, then we can use the orbit itinerary to recover the rotation number up to certain equivalences.     

Algebraic approach to the interval linear static identification,tolerance, and control problems,or one more application of kaucher arithmetic

In this paper, theidentification problem, thetolerance problem, and thecontrol problem are treated for the interval linear equation Ax=b. These problems require computing an inner approximation of theunited solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, of thetolerable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, and of thecontrollable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?b ∈ b)(Ax ∈b)} respectively. Analgebraic approach to their solution is developed in which the initial problem is replaced by that of finding analgebraic solution of some auxiliary interval linear system in Kaucher extended interval arithmetic. The algebraic approach is proved almost always to give inclusion-maximal inner interval estimates of the solutionsets considered. We investigate basic properties of the algebraic solutions to the interval linear systems and propose a number of numerical methods to compute them. In particular, we present the simple and fastsubdifferential Newton method, prove its convergence and discuss numerical experiments.     

Reactive systems, (semi-)saturated semantics and coalgebras on presheaves

The semantics of process calculi has traditionally been specified by labelled transition systems (ltss), but, with the development of name calculi, it turned out that reaction rules (i.e., unlabelled transition rules) are often more natural. This leads to the question of how behavioral equivalences (bisimilarity, trace equivalence, etc.) defined for lts can be transferred to unlabelled transition systems. Recently, in order to answer this question, several proposals have been made with the aim of automatically deriving an lts from reaction rules in such a way that the resulting equivalences are congruences. Furthermore, these equivalences should agree with the standard semantics, whenever one exists.In this paper, we propose saturated semantics, based on a weaker notion of observation and orthogonal to all the previous proposals, and we demonstrate the appropriateness of our semantics by means of two examples: logic programming and open Petri nets. We also show that saturated semantics can be efficiently characterized through the so called semi-saturated games. Finally, we provide coalgebraic models relying on presheaves.     

Adding Action Refinement to a Finite Process Algebra

In this paper we present a Process Algebra for the specification of concurrent, communicating processes which incorporates operators for the refinement of actions by processes, in addition to the usual operators for communication, nondeterminism, internal actions, and restrictions, and study a suitable notion of semantic equivalence for it. We argue that action refinements should not, in some formal sense, interfere with the internal evolution of processes and their application to processes should consider the restriction operator as a "binder." We show that, under the above assumptions, the weak version of the refine equivalence introduced by Aceto and Hennessy ((1993) Inform. and Comput.103, 204-269) is preserved by action refinements and, moreover, is the largest such equivalence relation contained in weak bismulation equivalence. We also discuss an example showing that, contrary to what happens in Aceto and Hennessy ((1993) Inform. and Comput.103, 204-269), refine equivalence and timed equivalence are different notions of equivalence over the language considered in this paper.     

A fully abstract semantics for causality in the \pi-calculus

We examine the meaning of causality in calculi for mobile processes like the -calculus, and we investigate the relationship between interleaving and causal semantics for such calculi. We separate two forms of causal dependencies on actions of -calculus processes, called subject and object dependencies: The former originate from the nesting of prefixes and are propagated through interactions among processes (they are the only form of causal dependencies present in CCS-like languages); the latter originate from the binding mechanisms on names. We propose a notion of causal bisimulation which distinguishes processes which differ for the subject or for the object dependencies. We show that this causal equivalence can be reconducted to, or implemented into, the ordinary interleaving observation equivalence. We prove that our encoding is fully abstract w.r.t. the two behavioural equivalences. This allows us to exploit the simpler theory of the interleaving semantics to reason about the causal one. In [San94b] a similar programme is carried out for location bisimulation [BCHK91], a non-interleaving spatial-sensitive (as opposed to causal-sensitive) behavioural equivalence. The comparison between the encodings of causal bisimulation in this paper, and of location bisimulation in [San94b], evidences the similarities and the differences between these two equivalences. Received 11 December 1995 / 16 June 1997     

Refining the Undecidability Border of Weak Bisimilarity

Weak bisimilarity is one of the most studied behavioural equivalences. This equivalence is undecidable for pushdown processes (PDA), process algebras (PA), and multiset automata (MSA, also known as parallel pushdown processes, PPDA). Its decidability is an open question for basic process algebras (BPA) and basic parallel processes (BPP). We move the undecidability border towards these classes by showing that the equivalence remains undecidable for weakly extended versions of BPA and BPP. In fact, we show that the weak bisimulation equivalence problem is undecidable even for normed subclasses of BPA and BPP extended with a finite constraint system.     

Efficient triangulation of simple polygons

This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a newadaptive algorithm for triangulating a simplen-sided polygon. The algorithm runs in timeO(n(1+t _o)) witht ₀<n. The quantityt ₀ measures theshape-complexity of thetriangulation delivered by the algorithm. More preciselyt ₀ is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of theinput polygon. Although the worst-case complexity of the algorithm isO(n ²), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where thecomputational complexity is a function of theoutput complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well.     

An impossibility about failure detectors in the iterated immediate snapshot model

The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”.     

Broadcast Calculus Interpreted in CCS upto Bisimulation

A function M is given that takes any process p in the calculus of broadcasting systems CBS and returns a CCS process M(p) with special actions {hear?, heard!, say?, said!} such that a broadcast of ω by p is matched by the sequence say? τ^* said(ω) by M(p) and a reception of υ by hear(v) τ^*heard!. It is shown that p M(p), where is a bisimulation equivalence using the above matches, and that M(p) has no CCS behaviour not covered by . Thus the abstraction of a globally synchronising broadcast can be implemented by sequences of local synchronisations. The criteria of correctness are unusual, and arguably stronger than requiring equivalences to be preserved — the latter does not guarantee that meaning is preserved. Since is not a native CCS equivalence, it is a matter of dicussion what the result says about Holmer's (CONCUR'93) conjecture, partially proved by Ene and Muntean (FCT'99), that CCS cannot interpret CBS upto preservation of equivalence.     

Equivalence hypothesis testing in experimental software engineering

This article introduces the application of equivalence hypothesis testing (EHT) into the Empirical Software Engineering field. Equivalence (also known as bioequivalence in pharmacological studies) is a statistical approach that answers the question "is product T equivalent to some other reference product R within some range $\Updelta$ ?." The approach of “null hypothesis significance test” used traditionally in Empirical Software Engineering seeks to assess evidence for differences between T and R, not equivalence. In this paper, we explain how EHT can be applied in Software Engineering, thereby extending it from its current application within pharmacological studies, to Empirical Software Engineering. We illustrate the application of EHT to Empirical Software Engineering, by re-examining the behavior of experts and novices when handling code with side effects compared to side-effect free code; a study previously investigated using traditional statistical testing. We also review two other previous published data of software engineering experiments: a dataset compared the comprehension of UML and OML specifications, and the last dataset studied the differences between the specification methods UML-B and B. The application of EHT allows us to extract additional conclusions to the previous results. EHT has an important application in Empirical Software Engineering, which motivate its wider adoption and use: EHT can be used to assess the statistical confidence with which we can claim that two software engineering methods, algorithms of techniques, are equivalent.     

Characterizing strong equivalence for argumentation frameworks

Since argumentation is an inherently dynamic process, it is of great importance to understand the effect of incorporating new information into given argumentation frameworks. In this work, we address this issue by analyzing equivalence between argumentation frameworks under the assumption that the frameworks in question are incomplete, i.e. further information might be added later to both frameworks simultaneously. In other words, instead of the standard notion of equivalence (which holds between two frameworks, if they possess the same extensions), we require here that frameworks F and G are also equivalent when conjoined with any further framework H. Due to the nonmonotonicity of argumentation semantics, this concept is different to (but obviously implies) the standard notion of equivalence. We thus call our new notion strong equivalence and study how strong equivalence can be decided with respect to the most important semantics for abstract argumentation frameworks. We also consider variants of strong equivalence in which we define equivalence with respect to the sets of arguments credulously (or skeptically) accepted, and restrict strong equivalence to augmentations H where no new arguments are raised.     

Mobility control via passports

Dπ is a simple distributed extension of the π-calculus in which agents are explicitly located, and may use an explicit migration construct to move between locations.In this paper, we introduce passports to control those migrations; in order to gain access to a location agents are now expected to show some credentials, granted by the destination location. Passports are tied to specific locations, from which migration is permitted. We describe a type system for these passports, which includes a novel use of dependent types, and prove that well-typing enforces the desired behaviour in migrating processes.Passports allow locations to control incoming processes. This induces major modifications to the observations which can be made of agent-based systems. Using the type system we describe these observations, and use them to build a loyal notion of observational equivalence for this setting. Finally we provide a complete proof technique in the form of a bisimilarity for establishing equivalences between systems.