
Marcus Kracht
Abstract. We call syntactic coding a technique which converts syntactic principles or constraints on representations into grammatical rules which can be implemented in any given rule grammar. In this paper we show that any principle or constraint on output trees formalizable in a certain fragment of dynamic logic over trees can be coded in this sense. This allows to reduce in a mechanical fashion most of the current theories of government and binding into gpsgstyle grammars. This will be exemplified with Rizzi’s Relativized Minimality. Key words: government and binding, relativized minimality, gpsg, dynamic logic 1.

Velko Iltchev
Abstract: The paper proposes a seminaive method for processing recursive loops in the dependency graph for a given query. The process goes through two phases. During the expand phase answers are generated using translation to base conjunctions. Entries in recursive predicates with undistinguished arguments are also stored in the database for further processing. During the shrink phase the occurrences of recursive predicates in rulebodies are replaced with the answers already generated during the expand phase. Thus, the whole rulebody becomes a base conjunction, which generates new answers. The proposed method is suitable for queries with bound arguments. It reduces unnecessary...

We present a compiler that takes high level signal and image processing algorithms described in MATLAB and generates an optimized hardware for an FPGA with external memory. We propose a precision analysis algorithm to determine the minimum number of bits required by an integer variable and a combined precision and error analysis algorithm to infer the minimum number of bits required by a floating point variable. Our results show that on an average, our algorithms generate hardware requiring a factor of 5 less FPGA resources in terms of the Configurable Logic Blocks (CLBs) consumed as compared to the hardware generated...

Guizhen Yang; Michael Kifer
Abstract. Reification and anonymous resources are two of the more interesting features of RDF — an emerging standard for representing semantic information on the Web. Ironically, when RDF was standardized by W3C over three years ago [18], it came without a semantics. There is now growing understanding that a Semantic Web language without a semantics is an oxymoron, and a number of efforts are directed towards giving RDF a precise semantics [12, 10]. In this paper we propose a simple semantics for reification and anonymous resources in Flogic [17] — a framebased logic language, which is a popular formalism for...

Konstantine Arkoudas; Selmer Bringsjord
Abstract. We present an encoding of a sequent calculus for a multiagent epistemic logic in Athena, an interactive theorem proving system for manysorted firstorder logic. We then use Athena as a metalanguage in order to reason about the multiagent logic an as object language. This facilitates theorem proving in the multiagent logic in several ways. First, it lets us marshal the highly efficient theorem provers for classical firstorder logic that are integrated with Athena for the purpose of doing proofs in the multiagent logic. Second, unlike modeltheoretic embeddings of modal logics into classical firstorder logic, our proofs are directly convertible...

Foad Dabiri; Ani Nahapetian; Miodrag Potkonjak; Majid Sarrafzadeh
Power consumption has emerged as the premier and most constraining aspect in modern microprocessor and application specific designs. Gate sizing has been shown to be one of the most effective methods for power (and area) reduction in CMOS digital circuits. Recently, as the feature size of logic gates (and transistors) is becoming smaller and smaller, the effect of soft error rates caused by single event upsets (SEU) is becoming exponentially greater. As a consequence of technology feature size reduction, the SEU rate for typical microprocessor logic at the sea level will go from one in hundred years to one every...

imperfect user preferences

Roman Barták
„Were you to ask me which programming paradigm is likely to gain most in commercial significance over the next 5 years I’d have to pick Constraint Logic Programming (CLP), even though it’s perhaps currently one of the least known and understood.” Dick Pountain, BYTE, February 1995

Christel Baier; Marcus Größer; Martin Leucker; Benedikt Bollig; Frank Ciesinski
Supported by the DFGProject “VERIAM ” and the DFGNWOProject “VOSS”. Supported by the European Research Training Network “Games”. Abstract Controller synthesis addresses the question of how to limit the internal behavior of a given implementation to meet its specification, regardless of the behavior enforced by the environment. In this paper, we consider a model with probabilism and nondeterminism where the nondeterministic choices in some states are assumed to be controllable, while the others are under the control of an unpredictable environment. We first consider probabilistic computation tree logic as specification formalism, discuss the role of strategytypes for the controller and...

Lars Arge
Ordered BinaryDecision Diagrams (OBDD) are the stateoftheart data structure for boolean function manipulation and there exist several software packages for OBDD manipulation. OBDDs have been successfully used to solve problems in e.g. digitalsystems design, verification and testing, in mathematical logic, concurrent system design and in artificial intelligence. The OBDDs used in many of these applications quickly get larger than the avaliable main memory and it becomes essential to consider the problem of minimizing the Input/Output (I/O) communication. In this paper we analyze why existing OBDD manipulation algorithms perform poorly in an I/O environment and develop new I/Oefficient algorithms. 1

Jana Koehler Rainer Hauser
Modeldriven architectures (MDA) separate the business or application logic from the underlying platform technology and represent this logic with precise semantic models. These models are supposed to span the entire life cycle of a software system and ease the software production and maintenance tasks. Consequently, tools will be needed that support these tasks. In this paper, we present a method that implements modeldriven transformations between particular platformindependent (business view) and platformspecific (IT architectural) models. On the business level, we focus on business view models expressed in ADF or UML2, whereas on the IT architecture side we focus on serviceoriented architectures...

Jens Lehmann; Sebastian Bader; Pascal Hitzler
Artificial neural networks can be trained to perform excellently in many application areas. Whilst they can learn from raw data to solve sophisticated recognition and analysis problems, the acquired knowledge remains hidden within the network architecture and is not readily accessible for analysis or further use: Trained networks are black boxes. Recent research efforts therefore investigate the possibility to extract symbolic knowledge from trained networks, in order to analyze, validate, and reuse the structural insights gained implicitly during the training process. In this paper, we will study how knowledge in form of propositional logic programs can be obtained in such...

Christian G. Fermüller; Robert Kosik; Technische Universität Wien
Abstract. Two popular approaches to formalize adequate reasoning with vague propositions are usually deemed incompatible: On the one hand, there is supervaluation with respect to precisification spaces, which consist in collections of classical interpretations that represent admissible ways of making vague atomic statements precise. On the other hand, tnorm based fuzzy logics model truth functional reasoning, where reals in the unit interval [0,1] are interpreted as degrees of truth. We show that both types of reasoning can be combined within a single logic SŁ, that extends both: Łukasiewicz logic Ł and (classical) S5, where the modality corresponds to ‘... is...

Srividya Kona; Ajay Bansal; Gopal Gupta; Thomas D. Hite
Abstract. Serviceoriented computing is gaining wider acceptance. For Web services to become practical, an infrastructure needs to be supported that allows users and applications to discover, deploy, compose and synthesize services automatically. This automation can take place effectively only if formal semantic descriptions of Web services are available. In this paper we present an approach for automatic service discovery and composition with both syntactic and semantic description of Web services. In syntactic case, we use a repository of services described using WSDL (Web Service Description Language). In the semantic case, the services are described using USDL (Universal ServiceSemantics Description Language),...

Ralf Möller; Volker Haarslev; Michael Wessel
Abstract. Although description logic systems can adequately be used for representing and reasoning about incomplete information (e.g., for John we know he is French or Italian), in practical applications it can be assumed that (only) for some tasks the expressivity of description logics really comes into play whereas for building complete applications, it is often necessary to effectively solve instance retrieval problems with respect to largely deterministic knowledge. In this paper we present and analyze the main results we have found about how to contribute to this kind of scalability problem. We assume familiarity with description logics in general and...

Guilin Qi; Weiru Liu; David A. Bell; David H. Glass
We propose an adaptive approach to merging possibilistic knowledge bases that deploys multiple operators instead of a single operator in the merging process. The merging approach consists of two steps: the splitting step and the combination step. The splitting step splits each knowledge base into two subbases and then in the second step, different classes of subbases are combined using different operators. Our merging approach is applied to knowledge bases which are selfconsistent and results in a knowledge base which is also consistent. Two operators are proposed based on two different splitting methods. Both operators result in a possibilistic knowledge...

Viktor Kuncak; Martin Rinard
Typestate Checking and Regular Graph Constraints We introduce regular graph constraints and explore their decidability properties. The motivation for regular graph constraints is 1) type checking of changing types of objects in the presence of linked data structures, 2) shape analysis techniques, and 3) generalization of similar constraints over trees and grids. Typestate checking for recursive and potentially cyclic data structures requires verifying the validity of implication for regular graph constraints. The implication of regular graph constraints also arises in shape analysis algorithms such as roleanalysis and some analyses based on threevalued logic. Over the class of lists regular graph...

Ron Meyden; Kaile Su
This paper describes how symbolic techniques (in particular, OBDD’s) may be used to to implement an algorithm for model checking specifications in the logic of knowledge for a single agent operating with synchronous perfect recall in an environment of which it has incomplete knowledge. As an illustration of the utility of this algorithm, the paper shows how it may be used to verify a security protocol: Chaum’s Dining Cryptographers protocol, which provides a mechanism for anonymous broadcast. It is argued that previous approaches to model checking security protocols are unable to verify this protocol, because of its information theoretic nature....

Discussed in this paper is a computing center management methodology based on the premise that the computer user’s time and work product are valuable. Experience in the use of interactive systems in a research environment from 1965 to the present time is presented. Current user experience and management of VMI CMS are emphasized. The use of computers as tools for extending users ’ powers of memory and logic and the development of new methods of managing VMICMS are discussed in detail. Managing VM/CMS systems for user effectiveness by W. J. Doherty and R. P. Kelisky This paper discusses the evolution...

Allan J Volponi; Tom Brotherton
Aircraft gasturbine engine data is available from a variety of sources including onboard sensor measurements, maintenance histories, and component models. An ultimate goal of Propulsion Health Management (PHM) is to maximize the amount of meaningful information that can be extracted from disparate data sources to obtain comprehensive diagnostic and prognostic knowledge regarding the health of the engine. Data Fusion is the integration of data or information from multiple sources, to achieve improved accuracy and more specific inferences than can be obtained from the use of a single sensor alone. The basic tenet underlying the data/information fusion concept is to leverage...