1.

Encoding A Dependent-Type lambda-Calculus In A Logic Programming Language
- Amy Felty; Dale Miller
Language Various forms of typed λ-calculi have been proposed as specification languages for representing wide varieties of object logics. The logical framework, LF, is an example of such a dependent-type λ-calculus. A small subset of intuitionistic logic with quantification over simply typed λ-calculus has also been proposed as a framework for specifying general logics. The logic of hereditary Harrop formulas with quantification at all non-predicate types, denoted here as hhω, is such a meta-logic that has been implemented in both the Isabelle theorem prover and the λProlog logic programming language. Both frameworks provide for specifications of logics in which details...

2.

An FPGA-Based Video Compressor for H.263 Compatible Bit Streams
- G. Lienhart R. Männer; R. Lay K. H. Noffz
This paper presents an FPGA architecture for video encoding according to the H.263 standard for video teleconferencing systems. The implementation is based on an off-the-shelf FPGA1 and is embedded in a PCI plug-in card2 with on-board SRAM plus external SRAM. The most complex part of the H.263 protocol, a base-line encoder, was implemented. The strategies, which have been applied to build the complex encoding operations, are treated in this paper. The complete application is able to operate at 30 MHz. This leads to a maximum compression speed of 120 Mbit/s allowing simultaneous real-time operation of several video streams in a...

3.

Normalization of industrial machinery with embedded devices and SOA
- Virgilio Gilart-iglesias; Francisco Maciá-pérez; Francisco José Mora-gimeno; José Vicente Berná-martínez
In the present paper we propose a method that permits visualization of manufacturing devices from a functional perspective. The aim of this method is to raise the abstraction level of manufacturing devices from the lower levels of production to the enterprise level of the business model. The target of this new approach is to integrate in a transparent way the resources, processes and, in general, the business logic of manufacturing levels using existing business models and achieving business continuity and process automation. The proposed method comprises two phases: the first phase that we have named industrial machinery normalization process; and...

4.

Quantitative Temporal Logic
- Yoram Hirshfeld; Er Rabinovich
We define a quantitative Temporal Logic that is based on a simple modality within the framework of Monadic Predicate Logic. Its canonical model is the real line (and not an !- sequence of some type). We prove its decidability using general theorems from Logic (and not Automata theory). We show that it is as expressive as any alternative suggested in the literature. Keywords: Quantitative Temporal Logic. Continuous time Model. 1 Introduction 1.1 Summary of the Results Temporal Logic (TL) is a convenient framework for reasoning about the evolving of a system in time. This made TL a popular subject in...

5.

Encoding Transition Systems in Sequent Calculus: Preliminary Report
- Raymond Mcdowell; Dale Miller; Catuscia Palamidessi
Linear logic has been used to specify the operational semantics of various process calculi. In this paper we explore how meta-level judgments, such as simulation and bisimulation, can be established using such encodings. In general, linear logic is too weak to derive such judgments and we focus on an extension to linear logic using definitions. We explore this extension in the context of transition systems. 1 Proof theory preliminaries In a recent note [5], Girard extended linear logic with a notion of definitions. If certain restrictions are placed on the structure of definitions then defined concepts have left and right...

6.

Characterizing D-WFS: Confluence and Iterated GCWA
- Stefan Brass; Jürgen Dix
. Quite recently Brass/Dix have introduced the semantics D-WFS for general disjunctive logic programs. The interesting feature of this approach is that it is both semantically and proof-theoretically founded. Any program \Phi is associated a normalform res(\Phi), called the residual program. We show in this paper, that the original calculus, consisting of some simple transformations, has a very strong and appealing property: it is confluent . This means that all the transformations can be applied in any order: if we arrive at an irreducible program (no more transformation is applicable) then this is already the unique normalform. No proper subset...

7.

Meeting the interlocking needs of LF-computation, deindexing, and inference: An organic approach to general NLU
- Chung Hee Hwang; Lenhart K. Schubert
We argue that a "theory bottleneck" encountered in the 70's and early 80's in attempts to build comprehensive NLU systems led to a fragmentation of NLU research, which still persists. To some extent, this fragmentation represents an appropriate response to the variety and subtlety of remaining problems; but at this point, it also represents a loss of nerve: NLU is an organic phenomenon, and enough has been learned about the vexing problems of the 80's to try to integrate these insights and build more comprehensive theories and extensible implementations. On that premise, we have been building such a comprehensive framework....

8.

A Decidable Predicate Logic of Knowledge
- Giorgi Japaridze; Giorgi Japaridze
The language we consider is that of classical first order logic augmented with the unary modal operator 2. Sentences of this language are regarded as true or false in a knowledge-base KB, which is any finite set of 2-free formulas. Truth of 2ff in KB is understood as that ff is true in all classical models of KB, and this interpretation is intended to capture the intuition "we know that ff" behind 2ff. The resulting logic is, in general, undecidable and not even semidecidable. However, there is a natural fragment of the above language, called the constructive language, which yields...

9.

Encoding Transition Systems in Sequent Calculus: Preliminary Report
- Raymond Mcdowell; Dale Miller; Catuscia Palamidessi
Linear logic has been used to specify the operational semantics of various process calculi. In this paper we explore how meta-level judgments, such as simulation and bisimulation, can be established using such encodings. In general, linear logic is too weak to derive such judgments and we focus on an extension to linear logic using definitions. We explore this extension in the context of transition systems. 1 Proof theory preliminaries In a recent note [5], Girard extended linear logic with a notion of definitions. If certain restrictions are placed on the structure of definitions then defined concepts have left and right...

10.

An Overview of Parallel Strategies for Transitive Closure on Algebraic Machines
- Filippo Cacace; Stefano Ceri; Maurice A. W. Houtsma
An important feature of database technology of the nineties is the use of distributed computation for speeding up the execution of complex queries. Today, the use of parallelism is tested in several experimental database architectures and a few commercial systems for conventional select-project-join queries. In particular, hash-based fragmentation is used to distribute data to disks under the control of different processors, in multi-processor architectures without shared memory, in order to perform selections and joins in parallel. With the development of new (logic) query languages and deductive databases, the new dimension of recursion has been added to query processing. Transitive closure...

11.

Equivalence of Well-Founded and Stable Semantics
- Françoise Gire
We show that the well-founded semantics and the stable semantics are equivalent on the class of the order-consistent programs which is a strict super-class of the locally-stratified programs class and of the call-consistent programs class. (1) Université de Paris 1 90 rue de Tolbiac 75634 Paris cedex 13 FRANCE email: gire@litp.ibp.fr 2 1 Introduction This paper deals with the equivalence problem of two well-known semantics which have been proposed for general logic programs: the stable semantics ([8]) and the well-founded semantics ([15,2]). A general logic program is a set of rules that have both positive and negative subgoals. Given a...

12.

Memoization in Constraint Logic Programming
- Mark Johnson
Motivated by a natural language processing application, this paper shows how to extend memoization techniques for logic programs to constraint logic programming. The lemma table proof procedure presented here generalizes standard memoization proof procedures such as OLDT resolution by (i) allowing goals and constraints to be resolved in any order, (ii) permitting memoization on sets of goals and constraints rather than only individual goals, and (iii) allowing the solutions recorded in the memo table to include unresolved goals and constraints, which are "inherited" by the calling routine. 1 Introduction This paper shows how to apply memoization (caching of subgoals and...

13.

Formal Methods: State of the Art and Future Directions
- Edmund M. Clarke; Jeannette M. Wing
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept, ACM Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissions@acm.org. 2 \Delta E.M. Clarke and J.M. Wing About Programs---Mechanical verification, Specification techniques; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic---Mechanical theorem proving General Terms: Software engineering, formal methods, hardware verification Additional Key Words and Phrases: Software specification, model checking, theorem proving 1....

14.

RASP: A General Logic Synthesis System for SRAM-based FPGAs
- Jason Cong; John Peck; Yuzheng Ding
In this paper, we present a general synthesis system for SRAM-based FPGAs named RASP. RASP consists of a core with a set of synthesis and optimization algorithms for technology independent logic synthesis and technology mapping for generating generic look-up tables (LUTs), together with a set of architecture-specific technology mapping routines to map the generic LUT network to programmable logic blocks (PLBs) for various SRAM-based FPGA architectures. Via a set of design representation converter routines, these architectureindependent and dependent synthesis algorithms are easily linked, and the entire system is seamlessly integrated into the design flow of commercial FPGA design systems. As...

15.

Tabled Evaluation with Delaying for General Logic Programs
- Weidong Chen; David S. Warren
SLD resolution with negation as finite failure (SLDNF) reflects the procedural interpretation of predicate calculus as a programming language and forms the computational basis for Prolog systems. Despite its advantages for stack-based memory management, SLDNF is often not appropriate for query evaluation for three reasons: a) it may not terminate due to infinite positive recursion; b) it may not terminate due to infinite recursion through negation; and c) it may repeatedly evaluate the same literal in a rule body, leading to unacceptable performance. We address all three problems for goal-oriented query evaluation of general logic programs by presenting tabled evaluation...

16.

Constraint Logic Programming: A Programming Approach to Teaching the Semantics of Logic *
- James Lu
. The problem of teaching the notion of logical consequence is discussed, and a solution proposed. The essential idea is to make concrete the abstract notion of interpretation through computer programs. Constraint Logic Programming appears to meet this idea nicely. 1. Introduction This paper analyzes a major conceptual difficulty students have in learning logic in general, and in learning the semantics of logic programming in particular. The difficulty is in understanding the notion of logical consequence (i.e. entailment). We show how Constraint Logic Programming (CLP) [2], a recent extension to classical logic programming, can be used to overcome this difficulty...

17.

Discourse ‘ Major Continuatives’ in a NonMonotonic Framework
- Jacques Jayez; Mathilde Dargnat; Université De Lyon (ens-lsh
Delattre (1966) proposed a classification of French basic melodic contours. He defined in particular ‘major continuatives ’ as melodic rises that mark the frontier between higher constituents in a hierarchy of clausal and sentential constituents. Although Delattre’s empirical basis for his classification has been discussed, there is a strong intuition that some sort of melodic rise can be used in French at the frontier between discourse constituents. The go al of this paper is to explore this possibility in two directions. First, we provide experimental evidence that, taken in isolation, major continuatives are not significantly discriminated from interrogative contours by...

18.

Nonstandard Ultra-logic-systems Applied to the GGU-model.
- Robert A. Herrmann
Abstract: This article develops and employs modern methods for mathemat-ical modeling. In particular, the methods of nonstandard analysis are ap-plied to general language logic-systems. This allows the operators for the only known mathematical cosmogony, the General Grand Unification Model (GGU-model), to more clearly exhibit their hyper-logical properties. All of the GGU-model entities and processes are predicted from observable entities and processes employed to construct physical entities. It is shown that, for each of the four cases for GGU-model interval construction and the four types of in-struction paradigms Iq, there exists an ultra-word-likeX q x such that when the hyper-algorithm ∗A...

19.

STATHIS PSILLOS CARNAP, THE RAMSEY-SENTENCE AND REALISTIC
ABSTRACT. Based on archival material from the Carnap and Feigl Archives, this paper re-examines Carnap’s approach to the issue of scientific realism in the 1950s and the early 1960s. It focuses on Carnap’s re-invention of the Ramsey-sentence approach to scientific theories and argues that Carnap wanted to entertain a genuine neutral stance in the realism-instrumentalism debate. Following Grover Maxwell, it claims that Carnap’s position may be best understood as a version of ‘structural realism’. However, thus understood, Carnap’s position faces the challenge that Newman raised against Russell’s structuralism: the claim that the knowledge of the unobservable is limited to its...

20.

INDUCTIVE LOGIC
The idea of inductive logic as providing a gene-ral, quantitative way of evaluating arguments is a relatively modern one. Aristotle’s conception of ‘induction ’ (epagog!Z)—which he contrasted with ‘reasoning ’ (sullogism!oB)—involved moving only from particulars to universals (Kneale and Kneale 1962, 36). This rather narrow way of think-ing about inductive reasoning seems to have held sway through the Middle Ages and into the seven-teenth century, when Francis Bacon (1620) devel-oped an elaborate account of such reasoning. During the eighteenth and nineteenth centuries, the scope of thinking about induction began to broaden considerably with the description of more sophisticated inductive techniques...