Outlier detection using default reasoning

Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems.     

A graph-based approach for extracting terminological properties from information sources with heterogeneous formats

The problem of handling both the integration and the cooperation of a large number of information sources characterised by heterogeneous representation formats is a challenging issue. In this context, a central role can be played by the knowledge about the semantic relationships holding between concepts belonging to different information sources (intersource properties). In this paper, we propose a semiautomatic approach for extracting two kinds of intersource properties, namely synonymies and homonymies, from heterogeneous information sources. In order to carry out the extraction task, we introduce both a conceptual model, for representing involved sources, and a metrics, for measuring the strength of the semantic relationships holding among concepts represented within the same source.     

Tice: A real-time language compilable using C++ compilers

Model-based development (MBD) holds the promise to capture potential timing problems in embedded software during the early phases of the development, securing the production of bug-free embedded software. For most MBD approaches, the source code is just an intermediate artifact that can be generated automatically from the models. This assumption clashes with an undeniable fact: a large share of the commercial embedded software exploits existing libraries or is developed using C/C++ natively. A way to reconcile the ambitions of MBD with the use of a programming language is by offering new language constructs and an innovative compilation tool-chain that prevents model error and timing problems “by construction.” However, the persistent popularity of C/C++ among embedded programmers and the limited availability of tools have severely limited the uptake of alternative programming languages for embedded software. Therefore, we propose an original route. Our language proposal, named Tice, has been shaped as a C++ active library. Tice retains full compatibility with existing C++ code, which can be integrated easily into new Tice-based projects. The enforcement of Tice syntax and semantics can be made by a standard C++ compiler, forgoing the need for new tools. In this article, we describe Tice's syntax, semantics, and model of computation and communication. We demonstrate Tice's practical applicability on an industrial scale use-case and give ample evidence for Tice's efficient compilation using off-the-shelf C++ compilers. Finally, we show Tice's code generation process.     

Intensional and extensional integration and abstraction of heterogeneous databases

This paper presents two techniques to integrate and abstract database schemes. The techniques assume the existence of a collection of interscheme properties describing semantic relationships holding among input database scheme objects. The former technique uses interscheme properties to produce an integrated scheme encoding a global, unified view of the whole semantics represented within input schemes. The latter one takes a (integrated) scheme as the input and yields in output an abstracted scheme encoding the same semantics as the input scheme, but represented at an higher, application-dependent abstraction level. In addition, the paper illustrates a possible application of these algorithms to the construction of a data repository. Finally, the paper presents the application of proposed techniques to some database schemes of Italian Central Governmental Offices.     

Efficient and robust probabilistic guarantees for real-time tasks

This paper presents a new method for providing probabilistic real-time guarantees to tasks scheduled through resource reservations. Previous work on probabilistic analysis of reservation-based schedulers is extended by improving the efficiency and robustness of the probability computation. Robustness is improved by accounting for a possibly incomplete knowledge of the distribution of the computation times (which is typical in realistic applications). The proposed approach computes a conservative bound for the probability of missing deadlines, based on the knowledge of the probability distributions of the execution times and of the inter-arrival times of the tasks. In this paper, such a bound is computed in realistic situations, comparing it with simulative results and with the exact computation of deadline miss probabilities (without pessimistic bounds). Finally, the impact of the incomplete knowledge of the execution times distribution is evaluated.     

QoS Management Through Adaptive Reservations

Reservation based (RB) scheduling is a class of scheduling algorithms that is well-suited for a large class of soft real-time applications. They are based on a bandwidth abstraction, meaning that a task is given the illusion of executing on a dedicated slower processor. In this context, a crucial design issue is deciding the bandwidth that each task should receive. The point we advocate is that, in presence of large fluctuations on the computation requirements of the tasks, it can be a beneficial choice to dynamically adapt the bandwidth based on QoS measurements and on the subsequent application of feedback control (adaptive reservations).In this paper, we present two novel contributions to this research area. First, we propose three new control algorithms inspired to the ideas of stochastic control. Second, we present a flexible and modular software architecture for adaptive reservations. An important feature of this architecture is that it is realised by means of a minimally invasive set of modifications to the Linux kernel.This work has been partially supported by the European OCERA IST-2001-35102 and RECSYS IST-2001-32515 projects.Luca Abeni is a Ph.D. in Computer Engineering at the Scuola Superiore SantAnna of Pisa (Italy). He graduated in Computer Engineering at the University of Pisa in 1998, and received a Ph.D. in Computer Engineering at the Scuola SuperioreS. Anna of Pisa in 2002. During 2000 he was a visiting student at the Carnegie Mellon University (Pittsburgh, PA), working with Prof. Ragunathan Rajkumar on resource reservation algorithms for real-time kernels. During 2001 he was a visiting student a Oregon Graduate Institute (Portland, OR) working with Prof. Jonathan Walpole on the support for time-sensitive applications in the Linux kernel. He has been working in Broadsat S.R.L. since 2003, developing audio/video streaming solutions and IPTV applications.Tommaso Cucinotta got the degree in Computer Engineering at the University of Pisa (Italy) in 2000. He got the Ph.D. inComputer Engineering at the Scuola Superiore SantAnna(SSSA) of Pisa in 2004 with a thesis titled Issues in authentication by means of smart-card devices. He held a course on cryptography in the International Master on Software Engineering organized at SSSA in 2002 and 2004. At the moment, he cooperates in research activities at the Scuola Superiore S. Anna in the areas of computer security and Quality of Service control for soft real-time systems.Giuseppe Lipari graduated in Computer Engineering at the University of Pisa in 1996, and received the Ph.D. degree in Computer Engineering from Scuola Superiore SantAnna in 2000. During 1999, he was avisiting student at University of North Carolina at Chapel Hill, collaborating with professor S.K. Baruah and professor K. Jeffay on real-time scheduling. Currently, he is assistant professor of Operating Systems with Scuola Superiore SantAnna. His main research activities are in real-time scheduling theory and its application to real-time operating systems, soft real-time systems for multimedia applications and component-based real-time systems.Luca Marzario is a Ph.D. student in Computer Engineering at the Scuola Superiore S. Anna of Pisa, Italy. In 2002, he graduated in Computer Engineering at University of Pisa. His main research interest include real-time systems scheduling, aperiodic service mechanism, feedback-scheduling, QoS in multimedia systems, Linux kernel and Real Time Linux executives (RTAI, RTLinux).Luigi Palopoli graduated in Control Engineering at the University of Pisa in 1998 and received his Ph.D. degree in Computer Engineering in 2002 from the Scuola Superiore S. Anna, Pisa. During 2001 he was a visiting scholar at the Department of EECS, University of California at Berkeley, where he worked on design techniques for real-time controllers under the supervision of Professor Alberto Sangiovanni-Vincentelli. He is currently Assistant Professor at the Scuola Superiore S. Anna (Pisa). His main research activities include Quality of Service control, control of systems under communication and computation constraints and design of embedded systems.     

Querying datalog with arrays: Design and implementation issues

This paper deals with the implementation of logic queries where array structures are manipulated. Both top-down and bottom-up implementations of the presented logic language, called Datalog ^A , are considered. Indeed, SLD-resolution is generalized to realize Datalog ^A top-down query answering. Further, a fixpoint based evaluation of Datalog ^A queries is introduced, which forms the basis for efficient bottom-up implementation of queries obtained by generalizing rewriting techniques such as magic set method to the case of Datalog ^A programs.Work partially supported by a European Union grant under the EC-US project DEUS EX MACHINA: nondeterminism for deductive databases and by a MURST grant (40% share) under the project Sistemi formali e strumenti per basi di dati evolute.     

Detecting and repairing anomalous evolutions in noisy environments

In systems where agents are required to interact with a partially known and dynamic world, sensors can be used to obtain knowledge about the environment. However, sensors may be unreliable, that is, they may deliver wrong information (due, e.g., to hardware or software malfunctioning) and, consequently, they may cause agents to take wrong decisions, which is a scenario that should be avoided. The paper considers the problem of reasoning in noisy environments in a setting where no (either certain or probabilistic) data is available in advance about the reliability of sensors. Therefore, assuming that each agent is equipped with a background theory encoding its general knowledge about the world, a concept of detecting an anomaly perceived in sensor data and the related concept of agent recovering to a coherent status of information are defined. In this context, the complexities of various anomaly detection and anomaly recovery problems are studied. Finally, rewriting algorithms are proposed that transform recovery problems into equivalent inference problems under answer set semantics, thereby making them effectively realizable on top of available answer set solvers.