110721.

IEC 1131-3 and the Instruction List Language
This article is about the weaknesses of part 3 of the IEC 1131
standard and in particular of one of the languages it defines called
Instruction List. It will also propose ways to improve the standard
so that it can be used to create high quality software.
1 Introduction
Traditionally when some control circuit was needed in for example a chemical plant, it would be
implemented using hardwired logic, i.e. a hardware circuit consisting of AND and NAND gates.
Unfortunately hardware circuits are inherently inflexible. The software implementation of Boolean
functions, called programmed logic, is much more flexible. Programmed logic uses a processor with
memory for a program, memory...

110722.

Experiences with a mechanisation of Martin-Lof's Theory of Types
- Gustavo Betarte
Martin-Lof's Theory of Types-MLTT- can be used as a logical framework in which other theories
can be defined. This paper describes ILF, a mechanisation of MLTT which allows definition of object
theories, judgement checking, reduction of expressions and other facilities for its use. An example of
how a particular object theory - Martin-Lof's Monomorphic Theory of Sets - can be defined in ILF
and used to develop correct programs is also presented.
Keywords : Logical Framework, Programming Logic, Martin-Lof's Theory of Types.
Both authors are partially supported by a PEDECIBA (Programa de Desarrollo de las Ciencias B'asicas) grant.
1 Introduction.
During the last two decades, as direct result...

110723.

An Overview of Hybrid Systems
- N. B. O. L. Pettit
"Hybrid systems" is a term that has recently started to appear with some frequency
at control conferences, with sessions dedicated to the topic and a workshop specifically
for the subject. This report tries to give a flavour of what people mean when talking
about hybrid systems. It will also try and assess whether there is any useful application
technology that might result from this research. Much of the material comes from an
invited workshop held on Block Island in September 1995. The proceedings from this are
now in print as a Springer Verlag monograph, "Control using Logic-Based Switching"
edited by S. Morse.
1
now at CF-T, Danfoss A/S, 6430...

110724.

STDL A Portable Language for Transaction Processing
- Philip A. Bernstein,Per O. Gyllstrom,Tom Wimberg
This paper
describes STDL's transaction features: transaction bracketing,
transactional remote procedure call, transactional queuing, recoverable
terminal I/O, and transactional exception handling.
STDL relies on standard C and COBOL for most application logic and
all operations on SQL databases and files. All transactional features of
STDL and new features outside standard C and COBOL are isolated in
procedures written in the STDL language. These procedures are called
tasks. This isolation of transactional features is quite different than
other persistent programming languages: one can use applications
written in standard C or COBOL; and to implement STDL, it is
possible to map clauses of task language onto operations of most any
distributed TP monitor.
Keywords: transactions,...

110725.

Generating Declarative Language Bias for Top-Down ILP Algorithms
- Stefan Kramer
Many of today's algorithms for Inductive Logic Programming (ILP)
put a heavy burden and responsibility on the user, because their declarative
bias have to be defined in a rather low-level fashion. To address this
issue, we developed a method for generating declarative language bias for
top-down ILP systems from high-level declarations. The key feature of our
approach is the distinction between a user level and an expert level of language
bias declarations. The expert provides abstract meta-declarations,
and the user declares the relationship between the meta-level and the given
database to obtain a low-level declarative language bias. The suggested
languages allow for compact and abstract specifications of the declarative
language...

110726.

Formalisation of Anaesthesiology for Decision Support
- Gerard R. Renardel De Lavalette,Rix Groenboom,Ernest Rotterdam,Frank Van Harmelen,Annette Ten Teije,Fred De Geus
This paper reports on research for decision support for anaesthesiologists
at the University Hospital in Groningen, the Netherlands. Based on Carola,
an existing automated operation documentation system, we design a support
environment that will assist in real-time diagnosis. The core of the work
presented here consists of a knowledge base (containing anaesthesiological
knowledge) and a diagnosis system. The knowledge base is specified in the
logic-based formal specification language AFSL. This leads to a powerful and
precise treatment of knowledge structuring and data abstraction.
Keywords anaesthesiology, formalisation of knowledge, data abstraction, diagnostic
reasoning
1 Introduction
We report in this paper on the research project FAN (Formalisation of ANaesthesiology)
. FAN aims to contribute...

110727.

Evaluating an Algorithm for Default Reasoning
- Ilkka Niemel,Patrik Simons
In this paper performance of a lately proposed
decision procedure for Reiter's default logic is
evaluated. Recent complexity results indicate
that there are two orthogonal sources of complexity
in default reasoning: classical (ørstorder)
reasoning and conAEict resolution (i.e.
choosing an appropriate set of applicable nonconAEicting
default rules). For classical reasoning
well-known techniques exist and conAEict
resolution presents the new computational
challenge in default reasoning. However, ef-
øcient conAEict resolution methods have been
lacking. The recently introduced default reasoning
algorithm pays special attention to conAEict
resolution and in this paper the eOEciency
of the conAEict resolution technique in the new
algorithm is examined. To rule out classical
reasoning, a fragment of default logic with only
atomic formulae is considered....

110728.

Learning with Extended Logic Programs
- Lu'is Moniz Pereira,Evelina Lamma,Fabrizio Riguzzi
We discuss the adoption of a three-valued setting for
inductive concept learning. Distinguishing between
what is true, what is false and what is unknown can be
useful in situations where decisions have to be taken
on the basis of scarce information. In a three-valued
setting, we want to learn a definition for both the target
concept and its opposite, considering positive and
negative examples as instances of two disjoint classes.
To this purpose, we adopt extended logic programs
under a well-founded semantics as the representation
formalism for learning. In this way, we are able to
represent both the concept and its opposite and deal
with incomplete or unknown information.
We discuss various approaches...

110729.

A Reactive Constraint Logic Programming Scheme
- F. Fages,J. Fowler
In this paper we present a constraint logic programming scheme for reactive systems.
A formal framework is developed to define the scheme's operational model and to
prove its completeness. A prototype implementation of a simplified version of this
model is described and then evaluated on two applications.
1 Introduction
The integration of constraint programming and logic programming resulted in a
powerful model of computation that is conceptually simple and semantically elegant
[6]. Constraint logic programming (CLP) systems have been proved successful
in complex system modeling and combinatorial optimization problems. A variety of
applications have been developed over the last decade across various application domains,
ranging from options trading and financial...

110730.

Research Report
- Intelligenz Gmbh,F. M. Donini,M. Lenzerini,D. Nardi,W. Nutt,Deutsches Forschungszentrum,K Unstliche Intelligenz
The basic feature of Terminological Knowledge Representation Systems is to represent
knowledge by means of taxonomies, here called terminologies, and to provide
a specialized reasoning engine to do inferences on these structures.
The taxonomy is built through a representation language called concept language
(or description logic), which is given well-defined set-theoretic semantics. The efficiency
of reasoning has often been advocated as a primary motivation for the use
of such systems.
Deduction methods and computational properties of reasoning problems in concept
languages are the subject of this paper. The main contributions of the paper
are: (1) a complexity analysis of concept satisfiability and subsumption for a wide
class of concept languages;...

110731.

Learning to Parse Database Queries Using Inductive Logic Programming
- John M. Zelle,Raymond J. Mooney
This paper presents recent work using the Chill
parser acquisition system to automate the construction
of a natural-language interface for database
queries. Chill treats parser acquisition as
the learning of search-control rules within a logic
program representing a shift-reduce parser and
uses techniques from Inductive Logic Programming
to learn relational control knowledge. Starting
with a general framework for constructing a
suitable logical form, Chill is able to train on a
corpus comprising sentences paired with database
queries and induce parsers that map subsequent
sentences directly into executable queries. Experimental
results with a complete database-query
application for U.S. geography show that Chill
is able to learn parsers that outperform a preexisting,
hand-crafted counterpart. These results
demonstrate the ability...

110732.

Unknown
- Chi-mei Yeung,Suet-mui Leung,Ho-fung Leung
Planning and scheduling are often NP-complete problems. There have
been different approaches to tackle these problems. With the emergence
of constraint logic programming, the constraint satisfaction approach has
started to attract attention due to its effectness in solving these real-life
problems. In this paper, we report our experience of applying constraint
logic programming to fully automate the time table scheduling process in
our faculty, which has been a tedious task for the administration. The system
consists of a core for scheduling as well as an X-window user interface.
Implemented in CHIP, the system consists of 1500 lines of codes, 80% of
which are an X-window user interface. The system...

110733.

Very Weak Zero One Law for Random Graphs With Order and Random Binary Functions
- Saharon Shelah
Introduction
In Compton Henson Shelah [CHSh245] it was proved that the zero one law fail for first order
logic, for ([n]; F n ), F n the random two place function (on [n] = f1; 2; : : : ; ng) where
Definition 0.1 The zero-one law for the logic L and random model M n means that for a
fixed vocabulary ø , for each natural number n, ¯ n is a probablity measure on a set K n of ø -
models, such that for each sentence / 2 L, the sequence hProb ¯n (M j= /) : n ! !i converge
to zero...

110734.

Mutable Object State for Object-Oriented Logic Programming: A Survey
- Vladimir Alexiev
One of the most difficult problems on the way to an integration of Object-Oriented and Logic
Programming is the modeling of changeable object state (i.e. object dynamics) in a particular
logic in order not to forfeit the declarative nature of LP. Classical logic is largely unsuitable
for such a task, because it adopts a general (both temporally and spatially), Platonic notion of
validity, whereas object state changes over time and is local to an object. This paper presents the
problem and surveys the state-of-the-art approaches to its solution, as well as some emerging,
promising new approaches. The paper tries to relate the different approaches, to evaluate...

110735.

Modelling Concurrency with Partial Orders
- Vaughan Pratt
Concurrency has been expressed variously in terms of formal languages (typically via
the shuffle operator), partial orders, and temporal logic, inter alia. In this paper we extract
from these three approaches a single hybrid approach having a rich language that mixes
algebra and logic and having a natural class of models of concurrent processes. The heart
of the approach is a notion of partial string derived from the view of a string as a linearly
ordered multiset by relaxing the linearity constraint, thereby permitting partially ordered
multisets or pomsets. Just as sets of strings form languages, so do sets of pomsets form
processes. We introduce a number...

110736.

Implementing Integrity Control in Active Databases
This paper presents an integrity maintenance system that has
been developed for maintaining static constraints in databases, using
the active database paradigm. This system has been added to
the O 2 object oriented database system, and is fully functional.
Constraints are specified by the user in a first order logic language,
and transformed in production rules, which are stored in
the database. The rules are then used to maintain the corresponding
set of constraints, for all applications that use the database,
and which no longer need to worry about integrity control. We
extend previous work on constraint maintenance in two ways: our
system can be used as a constraint maintenance...

110737.

PHI---A Logic-Based Tool for Intelligent Help Systems
- M. Bauer,S. Biundo,D. Dengler,J. Koehler,G. Paul
We introduce a logic-based system which improves
the performance of intelligent help systems
by supplying them with plan generation
and plan recognition components. Both
components work in close mutual cooperation.
There are two modes of cross-talk between
them, one where plan recognition is done on the
basis of abstract plans provided by the planner
and the other where optimal plans are generated
based on recognition results. The examples
which are presented are taken from an operating
system domain, namely from the unix mail
domain.
1 Introduction
Intelligent help systems aim at providing advanced active
help to the users of complex software systems (cf. [ Breuker,
1990; Thies and Berger, 1992; Norvig et al., 1993 ] ).
The...

110738.

Deductive Synthesis of Numerical Simulation Programs from Networks of Algebraic and Ordinary Differential Equations
- Thomas Ellman,Takahiro Murata
Scientists and engineers face recurring problems of constructing, testing and modifying numerical
simulation programs. The process of coding and revising such simulators is extremely
time-consuming, because they are almost always written in conventional programming languages.
Scientists and engineers can therefore benefit from software that facilitates construction
of programs for simulating physical systems. Our research adapts the methodology of
deductive program synthesis to the problem of constructing numerical simulation codes. We
have focused on simulators that can be represented as second order functional programs composed
of numerical integration and root extraction routines. We have developed a system that
uses first order Horn logic to synthesize numerical simulators built from...

110739.

Functional Pearls: Polytypic Unification
- Patrik Jansson,Johan Jeuring
Unification, or two-way pattern matching, is the process of solving an equation involving
two first-order terms with variables. Unification is used in type inference in many programming
languages and in the execution of logic programs. This means that unification
algorithms have to be written over and over again for different term types.
Many other functions also make sense for a large class of datatypes; examples are pretty
printers, equality checks, maps etc. They can be defined by induction on the structure of
user-defined datatypes. Implementations of these functions for different datatypes are
closely related to the structure of the datatypes. We call such functions polytypic.
This paper describes...

110740.

Concepts and Axioms
The paper discusses the transition from informal concepts to
mathematically precise notions; examples are given, and in some
detail the case of lawless sequences, a concept of intuitionistic
mathematics, is discussed. A final section comments on philosophical
discussions concerning intuitionistic logic in connection
with a "theory of meaning".
What I have to tell here is not a new story, and it does not contain
any really new ideas. The main difference with my earlier discussions
of the same topics ([TD88, chapter16],[Tro91]) is in the emphasis. This
paper starts with some examples of the transition from informal concepts
to mathematically precise notions, followed by a more detailed discussion
of one of these...