Bounded quantification and relations recognizable by finite automata

Summary The concept of inverse well-known for homomorphisms and gsm-mappings is extended to any language operation. The class IRP of language operations whose inverse preserves regularity is considered. As an application a necessary and sufficient condition is established for the class of relations recognizable by finite automata to be closed under different versions of bounded quantification.     

Relational similarity-based model of data part 1: foundations and query systems

We present a general rank-aware model of data which supports handling of similarity in relational databases. The model is based on the assumption that in many cases it is desirable to replace equalities on values in data tables by similarity relations expressing degrees to which the values are similar. In this context, we study various phenomena which emerge in the model, including similarity-based queries and similarity-based data dependencies. Central notion in our model is that of a ranked data table over domains with similarities which is our counterpart to the notion of relation on relation scheme from the classical relational model. Compared to other approaches which cover related problems, we do not propose a similarity-based or ranking module on top of the classical relational model. Instead, we generalize the very core of the model by replacing the classical, two-valued logic upon which the classical model is built by a more general logic involving a scale of truth degrees that, in addition to the classical truth degrees 0 and 1, contains intermediate truth degrees. While the classical truth degrees 0 and 1 represent nonequality and equality of values, and subsequently mismatch and match of queries, the intermediate truth degrees in the new model represent similarity of values and partial match of queries. Moreover, the truth functions of many-valued logical connectives in the new model serve to aggregate degrees of similarity. The presented approach is conceptually clean, logically sound, and retains most properties of the classical model while enabling us to employ new types of queries and data dependencies. Most importantly, similarity is not handled in an ad hoc way or by putting a “similarity module” atop the classical model in our approach. Rather, it is consistently viewed as a notion that generalizes and replaces equality in the very core of the relational model. We present fundamentals of the formal model and two equivalent query systems which are analogues of the classical relational algebra and domain relational calculus with range declarations. In the sequel to this paper, we deal with similarity-based dependencies.     

Relational similarity-based model of data part 2: dependencies in data

This paper is a sequel to our previous paper on relational similarity-based model of data and its fundamental query systems. The present paper elaborates on the dependency theory in the similarity-based model, focusing mainly on similarity-based functional dependencies, their semantic entailment, model-theoretic properties, complete axiomatizations, characterization of nonredundant bases, computational issues, and related algorithms. The paper shows that various aspects of dependencies in ranked data tables over domains with similarities can be properly formalized using complete residuated lattices as structures for similarities and ranks. In addition to their theoretical importance, the results can be directly applied in the areas of similarity-based constraints, query result analysis, and knowledge discovery from relational data which involves similarity-based reasoning. We assume that readers are acquainted with the prequel of this paper.     

Surgical and interventional robotics: part III [Tutorial]

Part I of this tutorial described two broad paradigms of interventional assistance: surgical computer-aided design (CAD)/computer-aided manufacturing (CAM) and surgical assistance. Part II focused on the underlying concepts of surgical CAD/CAM, with a particular emphasis on percutaneous procedures. This final installment of our three-part tutorial series discusses surgical assistance. In this section, we introduce the basic concepts of a surgical workstation and briefly review several core robotic technologies used in surgicalworkstations     

Event-based operational semantics and a consistency result for real-time concurrent processes with action refinement

In this paper an event-based operational interleaving semantics is proposed for real-time processes,for which action refinement and a denotational true concurrency semantics are developed and defined in terms of timed event structures. The authors characterize the timed event traces that are generated by the operational semantics in a denotational way, and show that this operational semantics is consistent with the denotational semantics in the sense that they generate the same set of timed event traces, thereby eliminating the gap between the true concurrency and interleaving semantics.     

Model-based construction and verification of critical systems using composition and partial refinement

This article introduces a new model-based method for incrementally constructing critical systems and illustrates its application to the development of fault-tolerant systems. The method relies on a special form of composition to combine software components and a set of proof rules to obtain high confidence of the correctness of the composed system. As in conventional component-based software development, two (or more) components are combined, but in contrast to many component-based approaches used in practice, which combine components consisting of code, our method combines components represented as state machine models. In the first phase of the method, a model is developed of the normal system behavior, and system properties are shown to hold in the model. In the second phase, a model of the required fault-handling behavior is developed and “or-composed” with the original system model to create a fault-tolerant extension which is, by construction, “fully faithful” (every execution possible in the normal system is possible in the fault-tolerant system). To model the fault-handling behavior, the set of states of the normal system model is extended through new state variables and new ranges for some existing state variables, and new fault-handling transitions are defined. Once constructed, the fault-tolerant extension is shown, using a set of property inheritance and compositional proof rules, to satisfy both the overall system properties, typically weakened, and selected fault-tolerance properties. These rules can often be used to verify the properties automatically. To provide a formal foundation for the method, formal notions of or-composition, partial refinement, fault-tolerant extension, and full faithfulness are introduced. To demonstrate and validate the method, we describe its application to a real-world, fault-tolerant avionics system.     

Task automata: Schedulability,decidability and undecidability

We present a model, task automata, for real time systems with non-uniformly recurring computation tasks. It is an extended version of timed automata with asynchronous processes that are computation tasks generated (or triggered) by timed events. Compared with classical task models for real time systems, task automata may be used to describe tasks (1) that are generated non-deterministically according to timing constraints in timed automata, (2) that may have interval execution times representing the best case and the worst case execution times, and (3) whose completion times may influence the releases of task instances. We generalize the classical notion of schedulability to task automata. A task automaton is schedulable if there exists a scheduling strategy such that all possible sequences of events generated by the automaton are schedulable in the sense that all associated tasks can be computed within their deadlines. Our first technical result is that the schedulability for a given scheduling strategy can be checked algorithmically for the class of task automata when the best case and the worst case execution times of tasks are equal. The proof is based on a decidable class of suspension automata: timed automata with bounded subtraction in which clocks may be updated by subtractions within a bounded zone. We shall also study the borderline between decidable and undecidable cases. Our second technical result shows that the schedulability checking problem will be undecidable if the following three conditions hold: (1) the execution times of tasks are intervals, (2) the precise finishing time of a task instance may influence new task releases, and (3) a task is allowed to preempt another running task.     

Quantifying statistical interdependence, part III: N > 2 point processes

Stochastic event synchrony (SES) is a recently proposed family of similarity measures. First, "events" are extracted from the given signals; next, one tries to align events across the different time series. The better the alignment, the more similar the N time series are considered to be. The similarity measures quantify the reliability of the events (the fraction of "nonaligned" events) and the timing precision. So far, SES has been developed for pairs of one-dimensional (Part I) and multidimensional (Part II) point processes. In this letter (Part III), SES is extended from pairs of signals to N > 2 signals. The alignment and SES parameters are again determined through statistical inference, more specifically, by alternating two steps: (1) estimating the SES parameters from a given alignment and (2), with the resulting estimates, refining the alignment. The SES parameters are computed by maximum a posteriori (MAP) estimation (step 1), in analogy to the pairwise case. The alignment (step?2) is solved by linear integer programming. In order to test the robustness and reliability of the proposed N-variate SES method, it is first applied to synthetic data. We show that N-variate SES results in more reliable estimates than bivariate SES. Next N-variate SES is applied to two problems in neuroscience: to quantify the firing reliability of Morris-Lecar neurons and to detect anomalies in EEG synchrony of patients with mild cognitive impairment. Those problems were also considered in Parts I and II, respectively. In both cases, the N-variate SES approach yields a more detailed analysis.     

Codes, automata, and continuous systems: Explicit interconnections

Close relationships are established between convolutional codes and zero-state automata and between cyclic codes and zero-input automata. Furthermore, techniques of automata theory and continuous system theory are used to elaborate on the coding problem; and approaches from coding and automata are used to establish and interpret typical structural conditions in continuous systems. The investigation incorporates basic coding concepts into the currently emerging common basis for automata and continuous systems, and it gives explicit examples of the resulting benefits accruing to each of these areas from the others.     

基于并发改进偏最小二乘的质量相关和过程相关的故障诊断

并发潜结构投影(CPLS)与传统贡献图法是多元统计过程监控中常用的故障检测与诊断方法.过程监控通常要求监测的时效性与诊断的准确性,然而,由于CPLS计算复杂以及传统贡献图诊断结果易受初始贡献较大的变量影响,因此它们反馈的监控结果可能并不准确.针对上述问题分别提出一种并发改进偏最小二乘(CMPLS)方法和新的相对贡献图法...     

Contexts, refinement and determinism

In this paper we have been influenced by those who take an “engineering view” of the problem of designing systems, i.e. a view that is motivated by what someone designing a real system will be concerned with, and what questions will arise as they work on their design. Specifically, we have borrowed from the testing work of Hennessy, de Nicola and van Glabbeek, e.g. Hennessy, 1988 [13], de Nicola [5], de Nicola, 1992 [21] and van Glabbeek, 2001, 1990 [40] and [39].Here we concentrate on one fundamental part of the engineering view and where consideration of it leads. The aspects we are concerned with are computational entities in contexts, observed by users. This leads to formalising design steps that are often left informal, and that in turn gives insights into non-determinism and ultimately leads to being able to use refinement in situations where existing techniques fail.     

Prefix codes,trees, and automata

We investigate the relations between the tree representation of a prefix code C, its patterns, the minimal automaton

which recognizes $\text{C}{}^1$, and the homomorphic images of the underlying algebra of

. These relations provide us with an appealing formulation which allows us to state (and eventually solve) some problems concerning the structure of prefix codes and therefore the structure of trees.     

Hybrid automata, reachability, and Systems Biology

Hybrid automata are a powerful formalism for the representation of systems evolving according to both discrete and continuous laws. Unfortunately, undecidability soon emerges when one tries to automatically verify hybrid automata properties. An important verification problem is the reachability one that demands to decide whether a set of points is reachable from a starting region.If we focus on semi-algebraic hybrid automata the reachability problem is semi-decidable. However, high computational costs have to be afforded to solve it. We analyse this problem by exploiting some existing tools and we show that even simple examples cannot be efficiently solved. It is necessary to introduce approximations to reduce the number of variables, since this is the main source of runtime requirements. We propose some standard approximation methods based on Taylor polynomials and ad hoc strategies. We implement our methods within the software SAHA-Tool and we show their effectiveness on two biological examples: the Repressilator and the Delta-Notch protein signaling.     

Action systems,unbounded nondeterminism,and infinite traces

Morgan [Mor90a] has described a correspondence between Back's action systems [BKS83] and the conventionalfailures-divergences model of Hoare'scommunicating sequential processes (CSP) formalism [Hoa85]. However, the CSP failures-divergences model does not treat unbounded nondeterminism, although unbounded nondeterminism arises quite naturally in action systems; to that extent, the correspondence between the two approaches is inadequate.Fortunately there is an extendedinfinite traces model of CSP [RoB89] which treats unbounded nondeterminism. We extend the CSP-action system correspondence, using that model instead, to take the unbounded nondeterminism of action systems properly into account.In passing, we develop a definition of the weakest precondition under which an infinite heterogeneous trace of actions is enabled.Funded by Broadcom Éireann Research Ltd, Dublin.     

Cellular automata,matrix substitutions and fractals

It has been observed that the long time evolution of a cellular automata (CA) can generate fractal sets. In this paper, we define a broad class of CA, all of which have a limit set. Moreover, we present an algorithm which associates with a CA of the above defined class a substitution system which deciphers the self-similarity structure of the limit set.Supported by DFG Forschungsgruppe Dynamische Systems.     

Shoreline evolution: GIS,remote sensing and cellular automata modelling

The evolution and more particularly the erosion of the coasts morphology is an important environmental subject. Both the study of the actual evolution of coasts via digital tools and their modelling for the sake of prediction are necessary. A study of the evolution of a section of the Algerian coastline with a geographical information system shows that erosion is the main factor for the shoreline evolution, in the absence of structures consolidating the beaches. Therefore, a qualitative numerical model of the erosion of a coastline is proposed. It relies on a coupling between a cellular automata sedimentation model and a bi-fluid hydrodynamical model based on the Lattice Boltzmann method. The current model is two-dimensional and simulates a cross-section of a virtual coastline. The virtual coastline exhibits a gradual erosion by the water, whose speed depends on the kind of perturbation applied on the water level.