
Mark Grechanik
Abstract. Two or more components (e.g., objects, modules, or programs) interoperate when they exchange data, such as XML data. Currently, there is no approach that can detect a situation at compile time when one component modifies XML data so that it becomes incompatible for use by other components, delaying discovery of errors to runtime. Our solution, a Verifier for Interoperating cOmponents for finding Logic fAults (Viola) builds abstract programs from the source code of components that exchange XML data. Viola symbolically executes these abstract programs thereby obtaining approximate specifications of the data that would be output by these components. The...

Joel David; Hamkins; Benedikt L Öwe
Abstract. A set theoretical assertion ψ is forceable or possible, written ✸ ψ, if ψ holds in some forcing extension, and necessary, written ✷ ψ, if ψ holds in all forcing extensions. In this forcing interpretation of modal logic, we establish that if zfc is consistent, then the zfcprovable principles of forcing are exactly those in the modal theory S4.2. 1.

Manuel G. Gericota; Luís F. Lemos; Gustavo R. Alves; José M. Ferreira
Abstract — The outstanding versatility of SRAMbased FPGAs make them the preferred choice for implementing complex customizable circuits. To increase the amount of logic available, manufacturers are using nanometric technologies to boost logic density and reduce prices. However, the use of nanometric scales also makes FPGAs particularly vulnerable to radiationinduced faults, especially because of the increasing amount of configuration memory cells that are necessary to define their functionality. This paper describes a framework for implementing circuits immune to radiationinduced faults, based on a customized Triple Modular Redundancy (TMR) infrastructure and on a detectionandfix controller. This controller is responsible for the...

This paper presents a new automatic synthesis technique for extended burstmode circuits, a class of asynchronous circuits that allow multipleinput changes between state transitions and a choice of next states based on input signal levels. The target implementation is a pseudostatic asymmetric CMOS complex gate per each output, known as generalized Celement [3, 12]. The synthesis algorithm generates hazardfree covers for set and reset functions of each output using Nowick and Dill’s exact hazardfree logic minimization algorithm [14]. Each output circuit is formed by mapping its set and reset logic to N and P stacks of an asymmetric CMOS gate...

The ISTLASAGNE project aims at designing and implementing the first, modular, scalable and truly alloptical photonic router capable of operating at 40 Gb/s. The main results achieved in the project are presented in this paper, with emphasis on the implementation of network node functionalities employing optical logic gates and optical flipflops, as well as an economical study on the proposed alloptical node architecture. Experimental results on clock recovery, packetrate clock recovery and 2bit label reading are provided employing optical gates based on active MachZehnder interferometers as the basic building block. The obtained results are very promising towards the goal of...

Xiaoliang Bai; Sujit Dey; Angela Krstić
As technology evolves into the deep submicron era, signal integrity problems are growing into a major challenge. An important source of signal integrity problems is the crosstalk noise generated by coupling capacitances between wires. Test vectors that activate and propagate crosstalk noise effects are becoming an essential part of design verification and manufacturing test. However, deriving such vectors is a complex task. In this paper, we propose HyAC, a fast yet accurate hybrid ATPG method targeting multipleaggressor induced crosstalk errors. Given a victim and a set of aggressors, the proposed ATPG method searches for test vectors to activate and propagate...

David Lorenzo Blanco; Dr. Alessandro Provetti
Dissertation presented at the Facultade de Informa'tica de A Corun~a following the requirements

Steven Eker; Patrick Lincoln; José Meseguer
Abstract. As the systems we have to specify and verify become larger and more complex, there is a mounting need to combine different tools and decision procedures to accomplish large proof tasks. The problem, then, is how to be sure that we can trust the correctness of a heterogeneous proof. In this work we focus on certification and synthesis of equational proofs, that are pervasive in most proof tasks and for which many tools are poorly equipped. Fortunately, equational proof engines like ELAN and Maude can perform millions of equational proof steps per second which, if certified by proof objects,...

article describes a formal semantics for the deontic concepts the concepts of permission and obligation — which arises naturally from the representations used in artificial intelligence systems Instead of treating deontic logic as a branch of modal logic, with the standard possible worlds semantics, we first develop a language for describing actions, and we define the concepts of permission and obligation in terms of these action descriptions. Using our semantic definitions, we then derive a number of intuitively plausible inferences, and we show generally that the paradoxes which are so frequently associated with deontic logic do not arise in our...

Brian R. Mestan
Conventional microprocessor designs treat register operands as atomic units. In such designs, no portion of an operand may be consumed until the entire operand has been produced. In practice, logic circuits and arithmetic units that generate some portion of an operand in advance of the remaining portions are both feasible and desirable, and have been employed in several existing designs. In this report, we propose to exploit the early partial knowledge of an instruction’s input operands for overlapping the execution of dependent instructions and resolving unknown dependences. In particular, four applications of partial operand knowledge are examined: bypassing partial operands,...

Faiz Arni; Shalom Tsur; Haixun Wang; Carlo Zaniolo
This paper describes the LDL++ system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the LDL++ language, while preserving its modeltheoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using LDL++ on various tested applications, such as middleware and datamining. 1


Takeshi Chusho; Ryousuke Yuasa; Shinpei Nishida; Katsuya Fujiwara
Abstract — The number of endusers using the Internet has been increasing. Enduser initiative development of applications has become important for automation of endusers ’ own tasks. In particular, Web applications should be supported by domain experts themselves since Web applications must be modified frequently based on domain experts ’ ideas. This paper describes enduser initiative application forms are considered as interfaces of services based on the simple concept that “one service = one form. ” Therefore, Web service integration can be defined as form transformation from input forms into output forms. There are two problems for development of Web...

Susan Cotterell; Frank Vahid
The advent of sensor networks has enabled a vast number of sensorbased applications such as monitoring forest fires, ensuring structural integrity of buildings or bridges, monitoring homes or offices, and others. However, sensor network application developers are often scientists, office workers, doctors, or homeowners, and not computer programmers, often not even engineers. Thus, setting up a sensor network can be cumbersome or costly. In this paper, we discuss experiments utilizing a set of electronic blocks, called eBlocks, that developers can use to build smallscale monitorcontrol systems. eBlocks are intended for nonexperts and do not require any programming or electronics experience....

Fernando Ferreira
Abstract. We study, within the framework of intuitionistic logic, two wellknown general results of (classical logic) bounded arithmetic. Firstly, Parikh’s theorem on the existence of bounding terms for the provably total functions. Secondly, the result which states that adding the scheme of bounded collection to (suitable) bounded theories does not yield new Π2 consequences.

Myla Archer; Constance Heitmeyer
Assuring the correctness of specifications of realtime systems can involve significant human effort. The use of a mechanical theorem prover to encode such specifications and to verify their properties could significantly reduce this effort. A barrier to routinely encoding and mechanically verifying specifications has been the need first to master the specification language and logic of a general theorem proving system. Our approach to overcoming this barrier is to provide mechanical support for producing specifications and verifying proofs, specialized for particular mathematical models and proof techniques. We are currently developing a mechanical verification system called TAME (Timed Automata Modeling Environment)...

Recent results in the foundations of probability theory indicate that a conditional probability can be viewed as a probability attached to a mathematical entity called a measurefree conditional. Such a measurefree conditional can receive a semantics in terms of a trivalent logic and logical operations are defined on conditionals in terms of truthtables. It is shown that these results can be useful to justify Cox's axiomatic framework for probability as well as its application to other theories of uncertainty (Shafer's plausibility functions and Zadeh's possibility measures). Moreover it is shown that measurefree conditionals have the properties of wellbehaved nonmonotonic inference...

Stefano Bistarelli; Ugo Montanari; Francesca Rossi
We extend the Constraint Logic Programming (CLP) formalism in order to handle semiringbased constraint systems. This allows us to perform in the same language both constraint solving and optimization. In fact, constraint systems based on semirings are able to model both classical constraint solving and more sophisticated features like uncertainty, probability, fuzzyness, and optimization. We then provide this class of languages with three equivalent semantics: modeltheoretic, fixpoint, and prooftheoretic, in the style of CLP programs. 1

Stasinos Konstantopoulos; Georgios Apostolikas
In this paper we describe a fuzzy Description Logic reasoner which implements resolution in order to provide reasoning services for expressive fuzzy DLs. The main innovation of this implementation is the ability to reason over assertions with abstract (unspecified) fuzzy degrees. The answer to queries is, consequently, an algebraic expression involving the (unknown) fuzzy degrees and the degree of the query. We describe the implementation and discuss a use case in the domain of semantic metaextraction where conventional DL reasoning is not applicable.

The goal of information extraction is to extract database records from text or semistructured sources. Traditionally, information extraction proceeds by first segmenting each candidate record separately, and then merging records that refer to the same entities. While computationally efficient, this approach is suboptimal, because it ignores the fact that segmenting one candidate record can help to segment similar ones. For example, resolving a wellsegmented field with a lessclear one can disambiguate the latter’s boundaries. In this paper we propose a joint approach to information extraction, where segmentation of all records and entity resolution are performed together in a single integrated...