
R. Elgueta; R. Jansana
Equality in firstorder logic is represented in the language by means of a logical symbol and so it is interpreted uniformly; the semantics says that its interpretation

Claudio Castellini
This paper is a summary of the author’s Ph.D. thesis, concerned with automated reasoning in quantified modal and temporal logics. The relevant contributions are: (i) a sound and complete set of sequent calculi for quantified modal logics is devised; (ii) the approach is extended to the quantified temporal logic of linear, discrete time and a framework for doing automated reasoning via Proof Planning in it is developed; (iii) a set of promising experimental results is shown, obtained by applying the framework to the problem of Feature Interactions in telecommunication systems.

Stéphane Demri A; Ranko Lazić B; David Nowak C
Constraint LTL, a generalisation of LTL over Presburger constraints, is often used as a formal language to specify the behavior of operational models with constraints. The freeze quantifier can be part of the language, as in some realtime logics, but this variablebinding mechanism is quite general and ubiquitous in many logical languages (firstorder temporal logics, hybrid logics, logics for sequence diagrams, navigation logics, logics with λabstraction etc.). We show that Constraint LTL over the simple domain 〈N, = 〉 augmented with the freeze quantifier is undecidable which is a surprising result in view of the poor language for constraints (only...

Zhiyuan He; Zebo Peng; Petru Eles; Paul Rosinger; Bashir M. Alhashimi
Abstract 1 High temperature has become a major problem for systemonchip testing. In order to reduce the test time while keeping the temperature of the chip under test within a safe range, a thermalaware test scheduling technique is required. This paper presents an approach to minimize the test time and, at the same time, prevent the temperature of cores under test going over the given upper limit. We employ test set partitioning to divide test sets into shorter test sequences, and add cooling spans between test sequences, so that overheating can be avoided. Moreover, test sequences from different test sets...

Capturing well typed references in DTDs Surprisingly enough, there has been few investigations for typing references of semistructured data and XML documents. This paper build on a previous proposal [7] introducing simple schemas with welltyped references and showing that such schemas, called normalized refschemas, are expressible as formulas of Hybrid Modal Logic. The aim of the present paper is to extend normalized refschemas in order to allow one for general regular expressions and provide a fully general notion of schema capturing welltyped references, called refschemas. The main contribution of the paper is to show that refschemas are still expressible in...

Default logic and the various forms of circumscription were developed to deal with similar problems. In this paper, we consider what is known about the relationships between the two approaches and present several new results extending this knowledge. We show that there are interesting cases in which the two formalisms do not correspond, as well as cases where default logic subsumes circumscription. We also consider positive and negative results on translating between defaults and circumscription, and develop a context in which they can be evaluated.

Giovanni Conforti; Damiano Macedonio; Vladimiro Sassone
Abstract. Bigraphs are emerging as an interesting model for concurrent calculi, like CCS, picalculus, and Petri nets. Bigraphs are built orthogonally on two structures: a hierarchical place graph for locations and a link (hyper)graph for connections. With the aim of describing bigraphical structures, we introduce a general framework for logics whose terms represent arrows in monoidal categories. We then instantiate the framework to bigraphical structures and obtain a logic that is a natural composition of a place graph logic and a link graph logic. We explore the concepts of separation and sharing in these logics and we prove that they...

Corina Cîrstea
We investigate logics for coalgebraic simulation from a compositional perspective. Specifically, we show that the expressiveness of an inductivelydefined language for coalgebras w.r.t. a given notion of simulation comes as a consequence of an expressivity condition between the language constructor used to define the language for coalgebras, and the relator used to define the notion of simulation. This result can be instantiated to obtain Baltag’s logics for coalgebraic simulation, as well as a logic which captures simulation on unlabelled probabilistic transition systems. Moreover, our approach is compositional w.r.t. coalgebraic types. This allows us to derive logics which capture other notions...

Olof Rensfelt; Olof Rensfelt
This report describes the porting of the ad hoc protocol LUNAR to the Bluetooth wireless technology. Typically ad hoc routing protocols are run over traditional broadcasting radio technologies such as IEEE 802.11b. Bluetooth however is connection orientated which means that the same network forming mechanisms used in other wireless technologies can not be used. The report describes the relevant parts of the Bluetooth stack followed by a description of the design decisions made during the implementation. There are two actual implementations described in the report. One designed to run on the Linux operating system in userspace, and another implementation where...

Hsinfu Lo
Cyclic redundancy codes (CRCs) form a powerful class of codes suited especially for the detection of burst errors in data storage and communication applications. In the traditional hardware implementation, a simple shiftregisterbased circuit performs the computation by handling the data one bit at a time. Parallel implementation can perform the necessary logic operations much faster than the serial implementation, therefore, it is very suitable to be applied in today’s highspeed systems employing CRC checking. In this paper, we describe the ways toward accomplishing two types of circuit design for parallel CRC computations. Our approach is to systematically decompose the original...

Contextual Taxonomies; D. Grossi; F. Dignum; J. j. Ch. Meyer
Abstract. In this work we propose a formalization of a notion of contextual taxonomy, that is to say, a taxonomy holding only with respect to a specific context. To this aim, a new proposal for dealing with “contexts as abstract mathematical entities ” is set forth, which is geared toward solving some problems arising in the area of normative system specifications for modeling multiagent systems. Contexts are interpreted as sets of description logic models for different languages, and a number of operations on contexts are defined. Using this framework, a simple scenario taken from the legal domain is modeled, and...

Joxan Jaffar; Michael J. Maher
Constraint Logic Programming (CLP) is a merger of two declarative paradigms: constraint solving and logic programming. Though a relatively new eld, CLP has progressed in several quite di erent directions. In particular, the early fundamental concepts have been adapted to better serve in di erent areas of applications. In this survey of CLP, a primary goal is to give a systematic description of the major trends in terms of common fundamental concepts. The three main parts cover the theory, implementation issues and programming for applications. 1.

Hasan Amjad
Abstract. The translation of the temporal logic CTL [2] into the modal µcalculus Lµ [10] is formalised in the HOL theorem prover [8]. 1

Taisuke Sato; Yoshitaka Kameya
We present an overview of symbolicstatistical modeling language PRISM whose programs are not only a probabilistic extension of logic programs but also able to learn from examples with the help of the EM learning algorithm. As a knowledge representation language appropriate for probabilistic reasoning, it can describe various types of symbolicstatistical modeling formalism known but unrelated so far in a single framework. We show by examples, together with learning results, that most popular probabilistic modeling formalisms, the hidden Markov model and Bayesian networks, are described by PRISM programs. 1

P. Bouyer; F. Laroussinie; Houda Bel Mokadem; Béatrice Bérard; Patricia Bouyer; François Laroussinie
Abstract. The context of this study is timed temporal logics for timed automata. In this paper, we propose an extension of the classical logic TCTL with a new Until modality, called “Until almost everywhere”. In the extended logic, it is possible, for instance, to express that a property is true at all positions of all runs, except on a negligible set of positions. Such properties are very convenient, for example in the framework of boolean program verification, where transitions result from changing variable values. We investigate the expressive power of this modality and in particular, we prove that it cannot...

Aravindan Raghuveer; Ewa Kusmierek; David Du
video streaming applications requires the server and/or client to be networkaware and adaptive. We present a dynamic rate and quality adaptation algorithm where the server varies its sending rate (without varying the quality level) to adapt to the network and client conditions and only as a last resort, does quality adaptation. We place the adaptation logic at the client since it has better knowledge about both the demand (buffer conditions, variable bitrate requirements) and supply (network conditions). Our approach is unique because the server’s sending rate is calculated based on the client’s varying demand (consumption rate) and the network status....

S. Nait Bahloul; Y. Amghar; M. Sayah
The object relational data model presents both the advantage of Codd's relational calculus power and the characteristics of the object orientation. Two major approaches have been adopted to satisfy the requirements of new databases applications. A first approach integrates the object characteristics into the new data models with the specification of data constraints and the definition of interrogation language. The second one, called evolutionary approach, keeps Codd's data model enriching with adequate concepts for the coverage of current database applications. In this approach and comparatively with studies presented by Melton, Date and Darwen have proposed the foundations of the object...

Denis Cousineau; Gilles Dowek
The lambdaPicalculus allows to express proofs of minimal predicate logic. It can be extended, in a very simple way, by adding computation rules. This leads to the lambdaPicalculus modulo. We show in this paper that this simple extension is surprisingly expressive and, in particular, that all functional Pure Type Systems, such as the system F, or the Calculus of Constructions, can be embedded in it. And, moreover, that this embedding is conservative under termination hypothesis.

Lap Poon Rupert Tang

My experience as a graduate student spans several areas in computer architecture and VLSI, including circuit analysis, physical design, logic design, verification, processor microarchitecture, and application studies. My dissertation research focuses on the design of the TRIPS architecture and its polymorphous capabilities. In the TRIPS chip implementation project, I led the microarchitecture specification, hardware verification, and physical design, and through this experience developed an extensive set of skills spanning a wide spectrum of computer system design. In this statement, I summarize the contributions of my dissertation research, describe my role in the implementation of the TRIPS chip, and outline my...