Expressing Priorities and External Probabilities in Process Algebra via Mixed Open/Closed Systems

Defining operational semantics for a process algebra is often based either on labeled transition systems that account for interaction with a context or on the so-called reduction semantics: we assume to have a representation of the whole system and we compute unlabeled reduction transitions (leading to a distribution over states in the probabilistic case). In this paper we consider mixed models with states where the system is still open (towards interaction with a context) and states where the system is already closed. The idea is that (open) parts of a system “P” can be closed via an operator “P↑G” that turns already synchronized actions whose “handle” is specified inside “G” into prioritized reduction transitions (and, therefore, states performing them into closed states). We show that we can use the operator “P↑G” to express multi-level priorities and external probabilistic choices (by assigning weights to handles inside G), and that, by considering reduction transitions as the only unobservable τ transitions, the proposed technique is compatible, for process algebra with general recursion, with both standard (probabilistic) observational congruence and a notion of equivalence which aggregates reduction transitions in a (much more aggregating) trace based manner. We also observe that the trace-based aggregated transition system can be obtained directly in operational semantics and we present the “aggregating” semantics. Finally, we discuss how the open/closed approach can be used to also express discrete and continuous (exponential probabilistic) time and we show that, in such timed contexts, the trace-based equivalence can aggregate more with respect to traditional lumping based equivalences over Markov Chains.     

Modelling and solving the intrusion detection problem in computer networks

We introduce a novel anomaly intrusion detection method based on a Within-Class Dissimilarity, WCD. This approach functions by using an appropriate metric WCD to measure the distance between an unknown user and a known user defined respectively by their profile vectors. First of all, each user performs a set of commands (events) on a given system (Unix for example). The events vector of a given user profile is a binary vector, such that an element of this vector is equal to “1” if an event happens, and to “0” otherwise. In addition to this, each user's class k has a typical profile defined by the vector P_k, in order to test if a new user i defined by its profile vector P_i belongs to the same class k or not. The P_k vector is a weighted events vector E_k, such that each weight represents the number of occurrences of an event e_k. If the “distance” d_ki (measured by a dissimilarity parameter) between an unknown profile P_i and a known profile P_k is reasonable according to a given threshold and to some constraints, then there is no intrusion. Else, the user i is suspicious. A simple example illustrates the WCD procedure. A survey of intrusion detection methods is presented.Our proposed method based on clustering users and using simple statistical formulas is very easy for implementation.     

A simple algorithm for the unique characterization of convex polygons

A simple method for specifying the shape and orientation of a convex polygon is described. The method utilizes eigenvalues and eigenvectors of a “moment of inertia” or mass matrix computed from the nodal coordinates of the polygon. The “shape” is characterized then by the parameter ( , where ξ₁ and ξ₂ are the eigenvalues (ξ₁ ξ₂), and the orientation by the axial direction of the first eigenvector. FORTRAN subroutines are provided for this algorithm.     

Completeness of Continuation Models for λμ-Calculus

We show that a certain simple call-by-name continuation semantics of Parigot's λ_μ-calculus is complete. More precisely, for every λ_μ-theory we construct a cartesian closed category such that the ensuing continuation-style interpretation of λ_μ, which maps terms to functions sending abstract continuations to responses, is full and faithful. Thus, any λ_μ-category in the sense of L. Ong (1996, in “Proceedings of LICS '96,” IEEE Press, New York) is isomorphic to a continuation model (Y. Lafont, B. Reus, and T. Streicher, “Continuous Semantics or Expressing Implication by Negation,” Technical Report 93-21, University of Munich) derived from a cartesian-closed category of continuations. We also extend this result to a later call-by-value version of λ_μ developed by C.-H. L. Ong and C. A. Stewart (1997, in “Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Paris, January 1997,” Assoc. Comput. Mach. Press, New York).     

Languages Defined with Modular Counting Quantifiers

We prove that a regular language defined by a boolean combination of generalized Σ₁-sentences built using modular counting quantifiers can be defined by a boolean combination of Σ₁-sentences in which only regular numerical predicates appear. The same statement, with “Σ₁” replaced by “first-order,” is equivalent to the conjecture that the nonuniform circuit complexity class ACC is strictly contained in NC¹. The argument introduces some new techniques, based on a combination of semigroup theory and Ramsey theory, which may shed some light on the general case.     

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n³) square submatrices ofTEXTin optimalO(n²) space. We identify 4ⁿ⁻¹families of indices forTEXT, each containing ∏ⁿ_i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n² log n) time andO(n²) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al.(in“Proceedings, Fourth Symposium on Theory of Computing,” pp. 125–136) for strings and matrices.     

First-Order Logic with Two Variables and Unary Temporal Logic

We investigate the power of first-order logic with only two variables over ω-words and finite words, a logic denoted by FO². We prove that FO² can express precisely the same properties as linear temporal logic with only the unary temporal operators: “next,” “previously,” “sometime in the future,” and “sometime in the past,” a logic we denote by unary-TL Moreover, our translation from FO² to unary-TL converts every FO² formula to an equivalent unary-TL formula that is at most exponentially larger and whose operator depth is at most twice the quantifier depth of the first-order formula. We show that this translation is essentially optimal. While satisfiability for full linear temporal logic, as well as for unary-TL, is known to be PSPACE-complete, we prove that satisfiability for FO² is NEXP-complete, in sharp contrast to the fact that satisfiability for FO³ has nonelementary computational complexity. Our NEXP upper bound for FO² satisfiability has the advantage of being in terms of the quantifier depth of the input formula. It is obtained using a small model property for FO² of independent interest, namely, a satisfiable FO² formula has a model whose size is at most exponential in the quantifier depth of the formula. Using our translation from FO² to unary-TL we derive this small model property from a corresponding small model property for unary-TL. Our proof of the small model property for unary-TL is based on an analysis of unary-TL types.     

A logic for reasoning about probabilities

We consider a language for reasoning about probability which allows us to make statements such as “the probability of E₁ is less than ” and “the probability of E₁ is at least twice the probability of E₂,” where E₁ and E₂ are arbitrary events. We consider the case where all events are measurable (i.e., represent measurable sets) and the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) Nilsson's probabilistic logic. As we show elsewhere, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.     

A Temporal Logic for Proving Properties of Topologically General Executions

We present a generalization of the temporal propositional logic of linear time which is useful for stating and proving properties of the generic execution sequence of a parallel program or a non-deterministic program. The formal system we present is exactly that same as the third of three logics presented by Lehmann and Shelah (Information and Control53, 165–198 (1982)), but we give it a different semantics. The models are tree models of arbitrary size similar to those used in branching time temporal logic. The formulation we use allows us to state properties of the “co-meagre” family of paths, where the term “co-meagre” refers to a set whose complement is of the first category in Baire's classification looking at the set of paths in the model as a metric space. Our system is decidable, sound, and, complete for models of arbitrary size, but it has the finite model property; namely, every sentence having a model has a finite model.     

Specification in CTL+Past for Verification in CTL

We describe PCTL, a temporal logic extending CTL with connectives allowing to refer to the past of a current state. This incorporates the new N, “from now on,” combinator we recently introduced. PCTL has a branching future, but a determined, finite, and cumulative past. We argue this is the right choice for a semantical framework and show this through an extensive example. We investigate the feasibility of verification with PCTL and demonstrate how a translation-based approach allows model-checking specifications written in NCTL, a fragment of PCTL.     

Towards coalgebraic behaviourism

In this paper we show that it is possible to model observable behaviour of coalgebras independently from their internal dynamics, but within the general framework of representing behaviour by a map into a “final” coalgebra.In the first part of the paper we characterise Set-endofunctors F with the property that bisimilarity of elements of F-coalgebras coincides with having the same observable behaviour. We show that such functors have the final coalgebra of a rather simple nature, and preserve some weak pullbacks. We also show that this is the case if and only if F-bisimilarity corresponds to logical equivalence in the finitary fragment of the coalgebraic logic.In the second part of the paper, we present a construction of a “final” coalgebra that captures the observable behaviour of F-coalgebras. We keep the word “final” quoted since the object we are going to construct need not belong to the original category. The construction is carried out for arbitrary Set-endofunctor F, throughout the construction we remain in Set, but the price to pay is the introduction of new morphisms. The paper concludes with a hint to a possible application to modelling weak bisimilarity for coalgebras.     

Review of several stochastic speech unit models

Hidden Markov models are commonly used for speech unit modelling. This type of model is composed of a non-observable or “hidden” process, representing the temporal structure of the speech unit, and an observation process linking the hidden process with the acoustic parameters extracted from the speech signal.Different types of hidden processes (Markov chain, semi-Markov chain, “expanded-state” Markov chain) as well as different types of observation processes (discrete, continuous, semi-continuous—multiple processes) are reviewed, showing their relationships. The maximum likelihood estimation of two-stage stochastic process parameters is presented in an a posteriori probability formalism. An intepretation of the expectation-maximization algorithm is proposed and the practical learning algorithms for hidden Markov models and hidden semi-Markov models are compared in terms of computation structure, probabilistic justification and complexity.This presentation is illustrated by experiments on a multi-speaker 130 isolated word recognition system. The implementation techniques are detailed and the different combinations of state occupancy modelling techniques and observation modelling techniques are studied from a practical point of view.     

Preprocessing of Intractable Problems

Some computationally hard problems, e.g., deduction in logical knowledge bases– are such that part of an instance is known well before the rest of it, and remains the same for several subsequent instances of the problem. In these cases, it is useful to preprocess off-line this known part so as to simplify the remaining on-line problem. In this paper we investigate such a technique in the context of intractable, i.e., NP-hard, problems. Recent results in the literature show that not all NP-hard problems behave in the same way: for some of them preprocessing yields polynomial-time on-line simplified problems (we call them compilable), while for other ones their compilability implies some consequences that are considered unlikely. Our primary goal is to provide a sound methodology that can be used to either prove or disprove that a problem is compilable. To this end, we define new models of computation, complexity classes, and reductions. We find complete problems for such classes, “completeness” meaning they are “the less likely to be compilable.” We also investigate preprocessing that does not yield polynomial-time on-line algorithms, but generically “decreases” complexity. This leads us to define “hierarchies of compilability,” that are the analog of the polynomial hierarchy. A detailed comparison of our framework to the idea of “parameterized tractability” shows the differences between the two approaches.     

Bisimulation for Higher-Order Process Calculi

Ahigher-order process calculusis a calculus for communicating systems which contains higher-order constructs like communication of terms. We analyse the notion ofbisimulationin these calculi. We argue that both the standard definition of bisimulation (i.e., the one for CCS and related calculi), as well ashigher-order bisimulation[E. Astesiano, A. Giovini, and G. Reggio,in“STACS '88,” Lecture Notes in Computer Science, Vol. 294, pp. 207–226, Springer-Verlag, Berlin/New York, 1988; G. Boudol,in“TAPSOFT '89,” Lecture Notes in Computer Science, Vol. 351, pp. 149–161, Springer-Verlag, Berlin/New York, 1989; B. Thomsen, Ph.D. thesis, Dept. of Computing, Imperial College, 1990] are in general unsatisfactory, because of their over-discrimination. We propose and study a new form of bisimulation for such calculi, calledcontext bisimulation, which yields a more satisfactory discriminanting power. A drawback of context bisimulation is the heavy use of universal quantification in its definition, which is hard to handle in practice. To resolve this difficulty we introducetriggered bisimulationandnormal bisimulation, and we prove that they both coincide with context bisimulation. In the proof, we exploit thefactorisation theorem: When comparing the behaviour of two processes, it allows us to “isolate” subcomponents which might give differences, so that the analysis can be concentrated on them     

A Novel Stochastic Game Via the Quantitative μ-calculus

The quantitative μ-calculus qMμ extends the applicability of Kozen's standard μ-calculus [D. Kozen, Results on the propositional μ-calculus, Theoretical Computer Science 27 (1983) 333–354] to probabilistic systems. Subsequent to its introduction [C. Morgan, and A. McIver, A probabilistic temporal calculus based on expectations, in: L. Groves and S. Reeves, editors, Proc. Formal Methods Pacific '97 (1997), available at [PSG, Probabilistic Systems Group: Collected reports, http://web.comlab.ox.ac.uk/oucl/research/areas/probs/bibliography.html]; also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap. 9], M. Huth, and M. Kwiatkowska, Quantitative analysis and model checking, in: Proceedings of 12th annual IEEE Symposium on Logic in Computer Science, 1997] it has been developed by us [A. McIver, and C. Morgan, Games, probability and the quantitative μ-calculus qMu, in: Proc. LPAR, LNAI 2514 (2002), pp. 292–310, revised and expanded at [A. McIver, and C. Morgan, Results on the quantitative μ-calculus qMμ (2005), to appear in ACM TOCL]; also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap. 11], A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, A. McIver, and C. Morgan, Results on the quantitative μ-calculus qMμ (2005), to appear in ACM TOCL] and by others [L. de Alfaro, and R. Majumdar, Quantitative solution of omega-regular games, Journal of Computer and System Sciences 68 (2004) 374–397]. Beyond its natural application to define probabilistic temporal logic [C. Morgan, and A. McIver, An expectation-based model for probabilistic temporal logic, Logic Journal of the IGPL 7 (1999), pp. 779–804, also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap.10]], there are a number of other areas that benefit from its use.One application is stochastic two-player games, and the contribution of this paper is to depart from the usual notion of “absolute winning conditions” and to introduce a novel game in which players can “draw”.The extension is motivated by examples based on economic games: we propose an extension to qMμ so that they can be specified; we show that the extension can be expressed via a reduction to the original logic; and, via that reduction, we prove that the players can play optimally in the extended game using memoryless strategies.     

Distributed discrete-event simulation using null message algorithms on hypercube architectures

This paper explores several variants of the Chandy-Misra Null Message algorithm for distributed simulation. The Chandy-Misra algorithm is one of a class of “conservative” algorithms that maintains the correct order of simulation throughout the execution of the model by means of constraints on simulation time advance. The algorithms developed in this paper incorporate an “event-oriented” view of the physical process and message-passing. The effects of the computational workload to compute each event is related to speedup attained over an equivalent sequential simulation. The effects of network topology are investigated, and performance is evaluated for the variants on transmission of null messages. The performance analysis is supported with empirical results based on an implementation of the algorithm on an Intel iPSC 32-node hypercube multiprocessor. Results show that speedups over sequential simulation of greater than N, using N processors, can be achieved in some circumstances.     

Large-scale regulatory network analysis from microarray data: modified Bayesian network learning and association rule mining

We present two algorithms for learning large-scale gene regulatory networks from microarray data: a modified information-theory-based Bayesian network algorithm and a modified association rule algorithm. Simulation-based evaluation using six datasets indicated that both algorithms outperformed their unmodified counterparts, especially when analyzing large numbers of genes. Both algorithms learned about 20% (50% if directionality and relation type were not considered) of the relations in the actual models. In our empirical evaluation based on two real datasets, domain experts evaluated subsets of learned relations with high confidence and identified 20–30% to be “interesting” or “maybe interesting” as potential experiment hypotheses.     

Being bored? Recognising natural interest by extensive audiovisual integration for real-life application

Automatic detection of the level of human interest is of high relevance for many technical applications, such as automatic customer care or tutoring systems. However, the recognition of spontaneous interest in natural conversations independently of the subject remains a challenge. Identification of human affective states relying on single modalities only is often impossible, even for humans, since different modalities contain partially disjunctive cues. Multimodal approaches to human affect recognition generally are shown to boost recognition performance, yet are evaluated in restrictive laboratory settings only. Herein we introduce a fully automatic processing combination of Active–Appearance–Model-based facial expression, vision-based eye-activity estimation, acoustic features, linguistic analysis, non-linguistic vocalisations, and temporal context information in an early feature fusion process. We provide detailed subject-independent results for classification and regression of the Level of Interest using Support-Vector Machines on an audiovisual interest corpus (AVIC) consisting of spontaneous, conversational speech demonstrating “theoretical” effectiveness of the approach. Further, to evaluate the approach with regards to real-life usability a user-study is conducted for proof of “practical” effectiveness.     

Dimension elevation formula for Chebyshevian blossoms

A given polynomial of degree less than or equal to n naturally “blossoms” into a function of n variables called its blossom. Considered as a polynomial function of degree less than or equal to (n+1) it “blossoms” into a “new” blossom which is now a function of (n+1) variables. A classical formula expresses any value of this new blossom as a strictly convex combination of (n+1) values of the initial one. We establish a similar formula for Chebyshevian blossoms.