Search

In this paper, we present a study aimed at understanding whether the embodiment and humanlikeness of an artificial agent can affect people's spontaneous and instructed mimicry of its facial expressions. The study followed a mixed experimental design and revolved around an emotion recognition task. Participants were randomly assigned to one level of humanlikeness (between-subject variable: humanlike, characterlike, or morph facial texture of the artificial agents) and observed the facial expressions displayed by a human (control) and three artificial agents differing in embodiment (within-subject variable: video-recorded robot, physical robot, and virtual agent). To study both spontaneous and instructed facial mimicry, we divided the experimental sessions into two phases. In the first phase, we asked participants to observe and recognize the emotions displayed by the agents. In the second phase, we asked them to look at the agents' facial expressions, replicate their dynamics as closely as possible, and then identify the observed emotions. In both cases, we assessed participants' facial expressions with an automated Action Unit (AU) intensity detector. Contrary to our hypotheses, our results disclose that the agent that was perceived as the least uncanny, and most anthropomorphic, likable, and co-present, was the one spontaneously mimicked the least. Moreover, they show that instructed facial mimicry negatively predicts spontaneous facial mimicry. Further exploratory analyses revealed that spontaneous facial mimicry appeared when participants were less certain of the emotion they recognized. Hence, we postulate that an emotion recognition goal can flip the social value of facial mimicry as it transforms a likable artificial agent into a distractor., Comment: 27 pages, 8 figures, 7 tables (Submitted to Frontiers in Robotics and AI, Human-Robot Interaction)

International audience; Numerical solution methods for electromagnetic scattering problems lead to large systems of equations with millions or even billions of unknown variables. The coefficient matrices are dense, leading to large computational costs and storage requirements if direct methods are used. A commonly used technique is to instead form a hierarchical representation for the parts of the matrix that corresponds to far-field interactions. The overall computational cost and storage requirements can then be reduced to O(N log N). This still corresponds to a large-scale simulation that requires parallel implementation. The hierarchical algorithms are rather complex, both regarding data dependencies and communication patterns, making parallelization non-trivial. In this chapter, we describe two classes of algorithms in some detail, we provide a survey of existing solutions, we show results for a proof-of-concept implementation, and we provide various perspectives on different aspects of the problem. The list of authors is organized into three subgroups, Larsson and Zafari (coordination and proof-of-concept implementation), Righero, Francavilla, Giordanengo, Vipiana, and Vecchi (definition of and expertise relating to the application), Kessler, Ancourt, and Grelck (perspectives and parallel expertise).

The thoracic diaphragm is the muscle that drives the respiratory cycle of a human being. Using a system of partial differential equations (PDEs) that models linear elasticity we compute displacements and stresses in a two-dimensional cross section of the diaphragm in its contracted state. The boundary data consists of a mix of displacement and traction conditions. If these are imposed as they are, and the conditions are not compatible, this leads to reduced smoothness of the solution. Therefore, the boundary data is first smoothed using the least-squares radial basis function generated finite difference (RBF-FD) framework. Then the boundary conditions are reformulated as a Robin boundary condition with smooth coefficients. The same framework is also used to approximate the boundary curve of the diaphragm cross section based on data obtained from a slice of a computed tomography (CT) scan. To solve the PDE we employ the unfitted least-squares RBF-FD method. This makes it easier to handle the geometry of the diaphragm, which is thin and non-convex. We show numerically that our solution converges with high-order towards a finite element solution evaluated on a fine grid. Through this simplified numerical model we also gain an insight into the challenges associated with the diaphragm geometry and the boundary conditions before approaching a more complex three-dimensional model. The INVIVE project is funded by the Swedish Research Council, grant number 2016-04849.

International audience; In this paper, we study the problem of detecting early signs of Parkinson's disease during an indirect human-computer interaction via a computer mouse activated by a user. The experimental setup provides a signal determined by the screen pointer position. An appropriate choice of segments in the cursor position raw data provides a filtered signal from which a number of quantifiable criteria can be obtained. These dynamical features are derived based on control theory methods. Thanks to these indicators, a subsequent analysis allows the detection of users with tremor. Real-life data from patients with Parkinson's and healthy controls are used to illustrate our detection method.

International audience

Multilayer networks have been widely used to represent and analyze systems of interconnected entities where both the entities and their connections can be of different types. However, real multilayer networks can be difficult to analyze because of irrelevant information, such as layers not related to the objective of the analysis, because of their size, or because traditional methods defined to analyze simple networks do not have a straightforward extension able to handle multiple layers. Therefore, a number of methods have been devised in the literature to simplify multilayer networks with the objective of improving our ability to analyze them. In this article we provide a unified and practical taxonomy of existing simplification approaches, and we identify categories of multilayer network simplification methods that are still underdeveloped, as well as emerging trends., Accepted for publication in Computer Science Review, Elsevier

International audience; We introduce a propagator for pairs of Sum constraints, where the expressions in the sums respect a form of convexity. This propagator is parametric and can be instantiated for various concrete pairs, including Deviation, Spread, and the conjunction of Linear ≤ and Among. We show that despite its generality , our propagator is competitive in theory and practice with state-of-the-art propagators.

First this report presents a restricted set of finite transducers used to synthesise structural time-series constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series constraints where each constraint is explicitly described in terms of automata with registers.

Sampling from the conditional (or posterior) probability distribution of the latent states of a Hidden Markov Model, given the realization of the observed process, is a non-trivial problem in the context of Markov Chain Monte Carlo. To do this Andrieu et al. (2010) constructed a Markov kernel which leaves this conditional distribution invariant using a Particle Filter. From a practitioner's point of view, this Markov kernel attempts to mimic the act of sampling all the latent state variables as one block from the posterior distribution but for models where exact simulation is not possible. There are some recent theoretical results that establish the uniform ergodicity of this Markov kernel and that the mixing rate does not diminish provided the number of particles grows at least linearly with the number of latent states in the posterior. This gives rise to a cost, per application of the kernel, that is quadratic in the number of latent states which could be prohibitive for long observation sequences. We seek to answer an obvious but important question: is there a different implementation with a cost per-iteration that grows linearly with the number of latent states, but which is still stable in the sense that its mixing rate does not deteriorate? We address this problem using blocking strategies, which are easily parallelizable, and prove stability of the resulting sampler.

International audience; Correctly-rounded implementations of some elementary functions are recommended by the IEEE 754-2008 standard, which aims at ensuring portable and predictable floating-point computations. Such implementations require the solving of the Table Maker's Dilemma which implies a huge amount of computation time. These computations are embarrassingly and massively parallel, but present control flow divergence which limits performance at the SIMD parallelism level, whose share in the overall performance of current and forthcoming HPC architectures is increasing. In this paper, we show that efficiently solving the Table Maker's Dilemma on various multi-core and many-core SIMD architectures (CPUs, GPUs, Intel Xeon Phi) requires to jointly handle divergence at the algorithmic, programming and hardware levels in order to scale with the number of SIMD lanes. Depending on the architecture, the performance gains can reach 10.5x over divergent code, or be constrained by different limits that we detail.

International audience; A checker for a constraint on a variable sequence can often be compactly specified by an automaton, possibly with accumulators, that consumes the sequence of values taken by the variables; such an automaton can also be used to decompose its specified constraint into a conjunction of logical constraints. The inference achieved by this decomposition in a CP solver can be boosted by automatically generated implied constraints on the accumulators, provided the latter are updated in the automaton transitions by linear expressions. Automata with non-linear accumulator updates can be automatically synthesised for a large family of time-series constraints. In this paper, we describe and evaluate extensions to those techniques. First, we improve the automaton synthesis to generate automata with fewer accumulators. Second, we decompose a constraint specified by an automaton with accumulators into a conjunction of linear inequalities, for use by a MIP solver. Third, we generalise the implied constraint generation to cover the entire family of time-series constraints. The newly synthesised automata for time-series constraints outperform the old ones, for both the CP and MIP decompositions, and the generated implied constraints boost the inference, again for both the CP and MIP decompositions. We evaluate CP and MIP solvers on a prototypical application modelled using time-series constraints.

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.

International audience; We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of total function constraints together with a constraint that can be easily reified.

International audience; In regular inference, a regular language is inferred from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. One of the most well-known regular inference algorithms is the L∗ algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We extend Angluin's algorithm for on-line learning of regular languages to the setting of timed systems. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by deterministic event-recording automata (DERAs). We present three algorithms, TL∗sg, TL∗ nsg and TL∗s, for inference of DERAs. In TL∗sg and TL∗ nsg, we further restrict event-recording automata to be event-deterministic in the sense that each state has at most one outgoing transition per action; learning such an automaton becomes significantly more tractable. The algorithm TL∗ nsg builds on TL∗s g, by attempts to construct a smaller (in number of locations) automaton. Finally, TL∗s is a learning algorithm for a full class of deterministic event-recording automata, which infers a so called simple DERA, which is similar in spirit to the region graph.

The tree constraint partitions a directed graph into node-disjoint trees. In many practical applications that involve such a partition, there exist side constraints specifying requirements on tree count, node degrees, or precedences and incomparabilities within node subsets. We present a generalisation of the tree constraint that incorporates such side constraints. The key point of our approach is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints, in order to avoid thrashing during search. We describe filtering rules for this extended tree constraint and evaluate its effectiveness on three applications: the Hamiltonian path problem, the ordered disjoint paths problem, and the phylogenetic supertree problem.

International audience; This paper deals with identification of dynamic discrete-time errors-in-variables systems. The statistical accuracy of a least squares estimator based on third-order cumulants is analyzed. In particular, the asymptotic covariance matrix of the estimated parameters is derived. The results are supported by numerical simulation studies.

International audience; Modern processors employ large structures (IQ, LSQ, register file, etc.) to expose instruction-level parallelism (ILP) and memory-level parallelism (MLP). These resources are typically allocated to instructions in program order. This wastes resources by allocating resources to instructions that are not yet ready to be executed and by eagerly allocating resources to instructions that are not part of the application's critical path. This work explores the possibility of allocating pipeline resources only when needed to expose MLP, and thereby enabling a processor design with significantly smaller structures, without sacrificing performance. First we identify the classes of instructions that should not reserve resources in program order and evaluate the potential performance gains we could achieve by delaying their allocations. We then use this information to " park " such instructions in a simpler, and therefore more efficient , Long Term Parking (LTP) structure. The LTP stores instructions until they are ready to execute, without allocating pipeline resources, and thereby keeps the pipeline available for instructions that can generate further MLP. LTP can accurately and rapidly identify which instructions to park, park them before they execute, wake them when needed to preserve performance, and do so using a simple queue instead of a complex IQ. We show that even a very simple queue-based LTP design allows us to significantly reduce IQ (64 → 32) and register file (128 → 96) sizes while retaining MLP performance and improving energy efficiency.

International audience; Some constraint programming solvers and constraint modelling languages feature the Sort(L, P , S ) constraint, which holds if S is a nondecreasing rearrangement of the list L, the permutation being made explicit by the optional list P. However, such sortedness constraints do not seem to be used much in practice. We argue that reasons for this neglect are that it is impossible to require the underlying sort to be stable, so that Sort cannot be guaranteed to be a total-function constraint, and that L cannot contain tuples of variables, some of which form the key for the sort. To overcome these limitations, we introduce the StableKeysort constraint, decompose it using existing constraints, and propose a propagator. This new constraint enables a powerful modelling idiom, which we illustrate by elegant and scalable models of two problems that are otherwise hard to encode as constraint programs.

To maximize performance, out-of-order execution processors sometimes issue instructions without having the guarantee that operands will be available in time; e.g. loads are typically assumed to hit in the L1 cache and dependent instructions are issued accordingly. This form of speculation -- that we refer to as speculative scheduling -- has been used for two decades in real processors, but has received little attention from the research community. In particular, as pipeline depth grows, and the distance between the Issue and the Execute stages increases, it becomes critical to issue instructions dependent on variable-latency instructions as soon as possible rather than wait for the actual cycle at which the result becomes available. Unfortunately, due to the uncertain nature of speculative scheduling, the scheduler may wrongly issue an instruction that will not have its source(s) available on the bypass network when it reaches the Execute stage. In that event, the instruction is canceled and replayed, potentially impairing performance and increasing energy consumption. In this work, we do not present a new replay mechanism. Rather, we focus on ways to reduce the number of replays that are agnostic of the replay scheme. First, we propose an easily implementable, low-cost solution to reduce the number of replays caused by L1 bank conflicts. Schedule shifting always assumes that, given a dual-load issue capacity, the second load issued in a given cycle will be delayed because of a bank conflict. Its dependents are thus always issued with the corresponding delay. Second, we also improve on existing L1 hit/miss prediction schemes by taking into account instruction criticality. That is, for some criterion of criticality and for loads whose hit/miss behavior is hard to predict, we show that it is more cost-effective to stall dependents if the load is not predicted critical. In total, in our experiments assuming a 4-cycle issue-to-execute delay, we found that the majority of instruction replays caused by L1 data cache banks conflicts -- 78.0% -- and L1 hit mispredictions -- 96.5% -- can be avoided, thus leading to a 3.4% performance gain and a 13.4% decrease in the number of issued instructions, over a baseline pipeline with speculative scheduling.

We introduce an automata-theoretic method for the verification of distributed algorithms running on ring networks. In a distributed algorithm, an arbitrary number of processes cooperate to achieve a common goal (e.g., elect a leader). Processes have unique identifiers (pids) from an infinite, totally ordered domain. An algorithm proceeds in synchronous rounds, each round allowing a process to perform a bounded sequence of actions such as send or receive a pid, store it in some register, and compare register contents wrt. the associated total order. An algorithm is supposed to be correct independently of the number of processes. To specify correctness properties, we introduce a logic that can reason about processes and pids. Referring to leader election, it may say that, at the end of an execution, each process stores the maximum pid in some dedicated register. Since the verification of distributed algorithms is undecidable, we propose an underapproximation technique, which bounds the number of rounds. This is an appealing approach, as the number of rounds needed by a distributed algorithm to conclude is often exponentially smaller than the number of processes. We provide an automata-theoretic solution, reducing model checking to emptiness for alternating two-way automata on words. Overall, we show that round-bounded verification of distributed algorithms over rings is PSPACE-complete., 26 pages, 6 figures

Few studies have looked at blood pressure (BP) evolution after nephrectomy, except for in living kidney donors with no clinical relevant modifications. STAFF is a pilot, open-label, observational study to evaluate the feasibility of following BP by home blood pressure monitoring (HBPM) after nephrectomy for cancer.56 patients (66.1% previously treated for hypertension) were included between November 1, 2011, and December 31, 2012; 95.8% of the patients realized five of six primary end-points in HBPM, but the last monitoring session at 6 months was often lacking (60%) probably because of a lack of understanding. When BP was controlled before surgery, 36% of the patients underwent new hypertension or hypertension dysregulation, without any correlating factor found; 33% of the patients presented the presence of proteinuria or an increase during the follow-up. Previous hypertension or high body mass index were risk factors for proteinuria increase (p = 0.036 and 0.032) but not treatment by an renin-angiotensin system blocker. There was no statistical link between HTA control and proteinuria.Our study shows that most patients undergoing nephrectomy for cancer are able to follow HBPM. It should be encouraged for detecting high BP or proteinuria, especially if antiangiogenic therapies are envisaged because of the supplementary risk of hypertension and proteinuria induced by these treatments.

Motivation: Imaging mass spectrometry (IMS) is a maturating technique of molecular imaging. Confidence in the reproducible quality of IMS data is essential for its integration into routine use. However, the predominant method for assessing quality is visual examination, a time consuming, unstandardized and non-scalable approach. So far, the problem of assessing the quality has only been marginally addressed and existing measures do not account for the spatial information of IMS data. Importantly, no approach exists for unbiased evaluation of potential quality measures. Results: We propose a novel approach for evaluating potential measures by creating a gold-standard set using collective expert judgements upon which we evaluated image-based measures. To produce a gold standard, we engaged 80 IMS experts, each to rate the relative quality between 52 pairs of ion images from MALDI-TOF IMS datasets of rat brain coronal sections. Experts’ optional feedback on their expertise, the task and the survey showed that (i) they had diverse backgrounds and sufficient expertise, (ii) the task was properly understood, and (iii) the survey was comprehensible. A moderate inter-rater agreement was achieved with Krippendorff’s alpha of 0.5. A gold-standard set of 634 pairs of images with accompanying ratings was constructed and showed a high agreement of 0.85. Eight families of potential measures with a range of parameters and statistical descriptors, giving 143 in total, were evaluated. Both signal-to-noise and spatial chaos-based measures performed highly with a correlation of 0.7 to 0.9 with the gold standard ratings. Moreover, we showed that a composite measure with the linear coefficients (trained on the gold standard with regularized least squares optimization and lasso) showed a strong linear correlation of 0.94 and an accuracy of 0.98 in predicting which image in a pair was of higher quality. Availability and implementation: The anonymized data collected from the survey and the Matlab source code for data processing can be found at: https://github.com/alexandrovteam/IMS_quality. Contact: theodore.alexandrov@embl.de

International audience; We present a few challenges that we consider important to tackle for the future of constraint programming. The focus is put on simplifying the design and implementation of propagators in solvers.

International audience; Though several high-level application development (macroprogramming) approaches have been proposed in literature for wireless sensor networks (WSN), there is a need to enable support for expressing and supporting end-to-end non-functional constraints such as latency in WSN macroprograms. We augment an existing macroprogramming language and its compilation process to enable the specification of end-to-end requirements, and propose task mapping algorithms to satisfy those requirements through a constraint programming approach. Through evaluations on realistic application task graphs, we show that our constraint programming model can effectively capture the end-to-end requirements and efficiently solves the combinatorial problem introduced.

International audience; Multi-pushdowns communicating via queues are formal models of multi-threaded programs communicating via channels. They are turing powerful and much of the work on their verification has focussed on under-approximation techniques. Any error detected in the under-approximation implies an error in the system. However the successful verification of the under-approximation is not as useful if the system exhibits unverified behaviours. Our aim is to design controllers that observe/restrict the system so that it stays within the verified under-approximation. We identify some important properties that a good con- troller should satisfy. We consider an extensive under-approximation class, construct a distributed controller with the desired properties and also establish the decidability of verification problems for this class.

We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. This propagator is parametric and can be instantiated for various concrete pairs, including DEVIATION, SPREAD, and the conjunction of Sum and COUNT. We show that despite its generality, our propagator is competitive in theory and practice with state-of-the-art propagators. This work is supported by grants 2011-6133 and 2012-4908 of the Swedish Research Council (VR). We thank the reviewers for their constructive comments.

Constraints over finite sequences of variables are ubiquitous in sequencing and timetabling. Moreover, the wide variety of such constraints in practical applications led to general modelling techniques and generic propagation algorithms, often based on deterministic finite automata (DFA) and their extensions. We consider counter-DFAs (cDFA), which provide concise models for regular counting constraints, that is constraints over the number of times a regular-language pattern occurs in a sequence. We show how to enforce domain consistency in polynomial time for atmost and atleast regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be incremented by transitions. We also prove that the satisfaction of exact regular counting constraints is NP-hard and indicate that an incomplete algorithm for exact regular counting constraints is faster and provides more pruning than the existing propagator from [3]. Regular counting constraints are closely related to the CostRegular constraint but contribute both a natural abstraction and some computational advantages., Comment: Includes a SICStus Prolog source file with the propagator

International audience; We formulate a sound and complete assume-guarantee framework for reasoning compositionally about safety properties of component behaviours. The specification of a component, which constrains the temporal ordering of input and output interactions with the environment, is expressed in terms of two prefix-closed sets of traces: an assumption and guarantee. The framework supports dynamic reasoning about components and specifications, and includes rules for parallel composition, logical conjunction corresponding to independent development, and quotient for incremental synthesis. Practical applicability of the framework is demonstrated by considering a simple printing example.

In this deliverable, we document the progress of WP2 during the fourth year of the CONNECT project. Following the last reviews' recommendations, the work is organized into two main streams. One stream concerns a quantitative extension of the compositional specification theory devised during the previous two years, while the other integrates the WP2 CONNECTor algebra with the specification theory so as to support WP3 CONNECTor synthesis. In particular, the assume-guarantee reasoning framework developed for the compositional specification theory ensures that a CONNECTed system preserves global safety properties by just checking the local properties of its constituent components. The proposed quantitative extension of the compositional specification theory allows the modeling of the real-time performance of networked systems, in addition to enabling the synthesis of CONNECTors that are compatible with both the functional behavior and timing constraints of their environments. Finally, in order to integrate the CONNECTor algebra with the specification theory so as to support WP3 synthesis, we defined a method for the automated synthesis of modular CONNECTors. We prove that the behavior of such a CONNECTor is equivalent to the behaviour of a monolithic WP3 CONNECTor. All of the work is evaluated through an application to relevant CONNECT scenarios, e.g., the GMES (Global Monitoring for Environment and Security) scenario.

International audience; Rather than providing general challenges, we first focus on a small set of concrete questions that we think are worth investigating. This means by no way that other issues, such as integrating continuous and discrete constraints, are not important, but we preferred to state focussed challenges. We then make some points regarding the development of sustainable CP solvers and the way CP interacts with other computer science areas.

http://www.sherpa.ac.uk/romeo/issn/0269-8889/; Air traffic management (ATM) under its current paradigm is reaching its structural limits considering the continuously growing demand. The need for a decrease in traffic workload opens numerous problems for optimization, from capacity balancing to conflict solving, using many different degrees of freedom, such as re-routing, flight-level changes, or ground-holding schemes. These problems are usually of a large dimension (there are 30 000 daily flights in Europe in the year 2012) and highly combinatorial, hence challenging for current problem solving technologies. We give brief tutorials on ATM and constraint programming (CP), and survey the literature on deploying CP technology for modelling and solving combinatorial problems that occur in an ATM context.

We supply details of a compositional specification theory we have been working on for modelling connectors and components. This supports the operations of parallel composition, for examining the structural behaviour of networked systems, logical conjunction, for supporting independent development of components, and quotient for incremental development in the form of component/connector synthesis. Our framework, a portion of which is conceptually similar to interface automata, is unique in that we've provided the first definition of quotient that can act on components exhibiting non-determinism, as well as the first definition of conjunction on this flavour of model. A refinement preorder corresponding to safe-substitutivity allows for the seamless interchanging of components and connectors without violating environmental assumptions. Our formulation of refinement also ensures that the framework enjoys strong algebraic properties. These are necessary for reasoning about components and connectors in a compositional manner.

SICS T2012-02, http://soda.swedish-ict.se/5194/; We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of pure functional dependency constraints together with a constraint that can be easily reified. We first show how the core constraints of the Global Constraint Catalogue can be reified and we then identify several reification categories that apply to at least 82% of the constraints in the Global Constraint Catalogue.

International audience; This editorial introduces the special issue on Continuous-time model identification and briefly presents the selected papers.

International audience; Checking language inclusion between two nondeterministic B ̈ chi au- u tomata A and B is computationally hard (PSPACE-complete). However, several approaches which are efficient in many practical cases have been proposed. We build on one of these, which is known as the Ramsey-based approach. It has recently been shown that the basic Ramsey-based approach can be drastically optimized by using powerful subsumption techniques, which allow one to prune the search-space when looking for counterexamples to inclusion. While previous works only used subsumption based on set inclusion or forward simulation on A and B , we propose the following new techniques: (1) A larger subsumption rela- tion based on a combination of backward and forward simulations on A and B . (2) A method to additionally use forward simulation between A and B . (3) Ab- straction techniques that can speed up the computation and lead to early detection of counterexamples. The new algorithm was implemented and tested on automata derived from real-world model checking benchmarks, and on the Tabakov-Vardi random model, thus showing the usefulness of the proposed techniques.

Interoperability remains a fundamental challenge when connecting heterogeneous systems which encounter and spontaneously communicate with one another in pervasive computing environments. This challenge is exasperated by the highly heterogeneous technologies employed by each of the interacting parties, i.e., in terms of hardware, operating system, middleware protocols, and application protocols. The key aim of the CONNECT project is to drop this heterogeneity barrier and achieve universal interoperability. Here we report on the development of the overall CONNECT architecture that will underpin this solution; in this respect, we present the following contributions: i) an elicitation of interoperability requirements from a set of pervasive computing scenarios, ii) a survey of existing solutions to interoperability, iii) an initial view of the CONNECT architecture, and iv) a series of experiments to provide initial validation of the architecture.

The CONNECT Integrated Project aims to develop a novel networking infrastructure that will support composition of networked systems with on-the-fly connector synthesis. The role of this work package is to investigate the foundations and verification methods for composable connectors. In this deliverable, we set the scene for the formulation of the modelling framework by surveying existing connector modelling formalisms. We covered not only classical connector algebra formalisms, but also, where appropriate, their corresponding quantitative extensions. All formalisms have been evaluated against a set of key dimensions of interest agreed upon in the CONNECT project. Based on these investigations, we concluded that none of the modelling formalisms available at present satisfy our eight dimensions. We will use the outcome of the survey to guide the formulation of a compositional modelling formalism tailored to the specific requirements of the CONNECT project. Furthermore, we considered the range of non-functional properties that are of interest to CONNECT, and reviewed existing specification formalisms for capturing them, together with the corresponding modelchecking algorithms and tool support. Consequently, we described the scientific advances concerning model-checking algorithms and tools, which are partial contribution towards future deliverables: an approach for online verification (part of D2.2), automated abstraction-refinement for probabilistic realtime systems (part of D2.2 and D2.4), and compositional probabilistic verification within PRISM, to serve as a foundation of future research on quantitative assume-guarantee compositional reasoning (part of D2.2 and D2.4).

There are two main classes of methods for checking universality and language inclusion of Büchi-automata: Rank-based methods and Ramsey-based methods. While rank-based methods have a better worst-case complexity, Ramsey-based methods have been shown to be quite competitive in practice [10,9]. It was shown in [10] (for universality checking) that a simple subsumption technique, which avoids exploration of certain cases, greatly improves the performance of the Ramsey-based method. Here, we present a much more general subsumption technique for the Ramsey-based method, which is based on using simulation preorder on the states of the Büchi-automata. This technique applies to both universality and inclusion checking, yielding a substantial performance gain over the previous simple subsumption approach of [10].

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M, with the same constraint defined by a finite-state automaton A on each row of M and a global cardinality constraint gcc on each column of M. We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the gcc constraints from the automaton A. The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We evaluate the impact of our methods on a large set of nurse rostering problem instances. Lecture notes in computer science; 6140. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-18, 2010. Proceedings. Springer 2010

The original publication is available at www.springerlink.com; International audience; In this paper, we present the LearnLib, a library of tools for automata learning, which is explicitly designed for the systematic experimental analysis of the profile of available learning algorithms and corresponding optimizations. Its modular structure allows users to configure their own tailored learning scenarios, which exploit specific properties of their envisioned applications. As has been shown earlier, exploiting application-specific structural features enables optimizations that may lead to performance gains of several orders of magnitude, a necessary precondition to make automata learning applicable to realistic scenarios.

International audience; We present an expressiveness study of linearity and persistence of processes. We choose the pi-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We consider four fragments of the pi-calculus. Each one singles out a natural source of linearity/ persistence also present in other frameworks such as Concurrent Constraint Programming (CCP), Linear CCP, and several calculi for security. The study is presented by providing (or proving the non-existence of) encodings among the fragments, a processes-as-formulae interpretation and a reduction from Minsky machines.

Nous présentons une contrainte de partitionnement de graphe par des arbres sous contraintes de degré. Étant donné un graphe orienté G, la contrainte spécifie que toute solution est formée par N arbres, tels que le nombre de fils d'un sommet quelconque de G appartienne à un ensemble donné de valeurs. Il existe pour la contrainte d'arbre pure, introduite dans [2], une caractérisation complète polynomialement évaluable. Cependant, la prise en compte du nombre de fils de chaque sommet rend le problème d'existence d'une solution NP-complet. Nous montrons donc comment intégrer une relaxation polynomiale de la contrainte de degré, prenant en compte les différents aspects de la contrainte d'arbre pure. Enfin, nous présentons une première série de résultats partiels pratiques sur les problèmes (NP-complets) d'existence d'un chemin Hamiltonien et d'un arbre binaire couvrant dans le cas de graphes orientés quelconques.

In this paper, we apply acompositional proof technique to an automaticverification of the correctness ofFischer's mutual exclusion protocol. Itis demonstrated that the technique mayavoid the state-explosion problem. Ourcompositional technique has recently beenimplemented in a tool, CMC, which givesexperimental evidence that the size ofthe verification effort required of the techniqueonly grows polynomially in thesize of the number of processes in theprotocol. In particular, CMC verifies theprotocol for 50 processes within 172.3seconds and using only 32MB main memory.In contrast all existing verificationtools for timed systems will suffer fromthe state-explosion problem, and no toolhas to our knowledge succeeded in verifyingthe protocol for more than 11 processes.

The CONNECT Integrated Project aims at enabling continuous composition of networked systems, by developing techniques for synthesizing connectors. A prerequisite for synthesis is to learn about the interaction behavior of networked peers. The role of WP4 is to develop techniques for learning models of networked peers and middleware through exploratory interaction. During Y1 of CONNECT, exploratory work was performed to understand the requirements for learning techniques in the CONNECT process, and to develop concepts for using a priori knowledge about component interfaces as a basis for learning. During Y2, a major goal has been to develop techniques for automatically learning models of networked peers and middleware, based on the concepts developed during Y1 (cf. D4.1). This deliverable surveys the significant progress made on problems that are important for realizing this goal. We have developed techniques for drastically improving the efficiency of active learning, meaning to explore significantly larger parts of component behavior within a given time. We verified the power of our approaches by winning the ZULU challenge in competition with several very strong groups in the language learning community. We have also made significant breakthroughs for learning of rich models with data. We have developed a novel compact and intuitive automaton model for representing learned behavior in a canonical way. Canonicity is very helpful for organizing the resuls of exploratory interactions, since it allows the extension of stable techniques for learning classical finite-state automata (such as L ) to richer models with data. We confirm this by using the new automaton as a basis for an extension of L to richer automaton models. During Y1, we have identified abstractions as an important concept in the process of learning behavioral models of realistic systems: we introduce a method for refining a given abstraction when needed during the learning process. We also present a specialization of learning, which does not generate complete models of behavior, but concentrates on aspects that are relevant in a specific context. Finally, the deliverable reports on our efforts to learn non-functional properties, the development of a monitoring infrastructure, and further development of the learning tool infrastructure, based on LearnLib.