==================================
VOLUME 20 NUMBER 1 February 1996
==================================
1. A Mathematical Model for Describing Structured Items of Conceptual
Level
Vladimir A. Fomichov, Department of Discrete Mathematics, Faculty of
Mechanics and Mathematics, Moscow State University, Vorobyovy Hills,
119899 Moscow, Russia, E-mail: vaf@nw.math.msu.su
and Department of Math. Provision of Information-Processing and
Control Systems, Faculty of Applied Mathematics, Moscow State Inst. of
Electronics and Math. - Techn. Univ. Bol. Tryokhsvyatitelsky pereulok,
3/12, 109028 Moscow, Russia
pp. 5-32
Keywords: artificial intelligence, natural language processing, natural
language semantics, conceptual level, discourse, structured meaning,
semantic representation, mathematical model, formal language, integral
formal semantics, restricted K-calculus, restricted standard
K-language, terminological knowledge representation language, universal
metagrammar of conceptual structures, universal stationary metagrammar
of deep conceptual syntax
Abstract: A mathematical model is determined and investigated which is
destined for describing structured items of conceptual level, in
particular, for describing structured meanings (SMs) of natural
language (NL) sentences and discourses. It defines a new class of
calculuses called restricted K-calculuses and a new class of formal
languages called restricted standard K-languages. The model is a
modified propositional component of the theory of K-calculuses and
standard K-languages being the central const NL use.
The formal means provided by the model are convenient, in particular,
for describing SMs of discourses with references to the mentioned
entities and to the meanings of phrases or larger fragments of texts,
with complicated designations of sets, with definitions of concepts. It
is shown that the possibilities of the model to describe SMs of
sentences and discourses and to represent concepts considerably exceed
the possibilities of Montague Grammar, Situation Theory, Theory of
Generalized Quantifiers, etc.
It is pointed out that the results may be used, in particular, for
developing mathematical theory of NL use, or mathematical
linguocybernetics, creating new hybrid knowledge representation
systems, building very powerful and flexible languages of semantic
representations of texts. The model is considered as an important
contribution to the development of a Universal Metagrammar of
Conceptual Structures. The hypothesis is put forward that the model may
be interpreted as a variant of a Universal Stationary Metagrammar of
Deep Conceptual Syntax.
-------------------
2. A Logic for Conditional Recommendation
S. K. Das, William Penney Laboratory, Imperial College, London SW7 2AZ,
Phone: +44 171 594 8424, Fax: +44 171 594 8449, E-mail:
skd@doc.ic.ac.uk AND P. Hammond, Department of Computer Science, Brunel
University, Middlesex UB8 3PH, Phone: +44 1895 203393, Fax: +44 1895
251686, E-mail: P.Hammond@brunel.ac.uk
pp. 33-42
Keywords: conditional, decision support system, logic, recommendation
Abstract: A decision support system is a computerized system which
utilizes knowledge about a particular application area to help decision
makers by recommending suitable actions. An action is conditionally
recommendable when a set of conditions associated with it is expected
to be brought about in the state resulting from performing the action.
Conditional recommendations occur frequently in practical
decision-making contexts but their formal treatment is yet to be
explored. Our approach is to develop a modal propositional logic for
reasoning about conditional recommendations. The semantics of the logic
is studied in terms of possible worlds where transition from one state
to another is made by performing an action. The soundness and
completeness of the logic is established. We also discuss the
exploitation of logic to formalize update and integrity constraint
verification in knowledge bases.
-------------------
3. Rule-Generating Abduction for Recursive Prolog
Kouichi Hirata, Kyushu Institute of Technology, Kawazu 680-4, Iizuka
820, Japan, Phone: +81 948 29 7884, Fax: +81-948-29-7600, E-mail:
hirata@ai.kyutech.ac.jp
pp. 43-56
Keywords: rule-generating abduction, inductive logic programming,
generalization
Abstract: The rule-generating abduction is a kind of abduction which
generates a rule and proposes a hypothesis from a surprising fact. In
general, there may exist infinitely many rules and hypotheses to
explain such a surprising fact. Hence, we need to put some restriction
on the class of rules. In rule-generating abduction, only one
surprising fact is given. Hence, we also need to generalize the concept
of a surprising fact. When we deal with such generalizations we must
avoid overgeneralization. It should be determined whether or not a
generalization is overgeneral by an intended model. However, it is hard
to give such an intended model in advance in our rule-generating
abduction. In this paper, we introduce a syntactical formulation of
generalization, in which it can be determined whether or not a
generalization is overgeneral by the forms of atoms and substitutions.
On the other hand, by the restriction of rules, it suffices to consider
only two types of terms, constants and lists, and two types of
substitutions with these two terms. By using the above generalizations
and substitutions, we design an algorithm for rule-generating abduction,
which generates rules and proposes hypotheses in polynomial time with
respect to the length of a surprising fact. The number of rules and
hypotheses is at most the number of common terms in a surprising fact.
Furthermore, we show that a common term in some argument of a
surprising fact also appears in the same argument of the proposed
hypothesis by this algorithm.
-------------------
4. Bottom-up Layout Generation
Walter Hower, Department of Computer Science, University College Cork,
National University of Ireland, College Rd, Cork, Ireland,
E-mail: walter@cs.ucc.ie
pp. 57-64
Keywords: layout design, constraint satisfaction
Abstract: The constraint satisfaction problem (CSP) comprises a set of
n variables with associated finite domains, and some combinations of
value assignments (``constraints'') to the variables; then, in order to
get the globally consistent solution, we need to compute the set of all
n-tuples consistent with the given constraints. Here we consider a
CSP modeling of a layout problem where we have to place rectangles
(``objects'') inside a target frame such that the objects do not
overlap. However, we further constrain the problem to obey the
following requirements: (a) Try to compute all layout possibilities.
(Just the answer whether a layout exists at all or to compute only one
possibility should not suffice.) (b) The user shall be able to interact
with the (semi-) automatic layout system in a way such that s/he may
pick an object to place it in a subarea, offered by the system, in an
arbitrary manner without the need to think about the placement of the
other objects. (After an algorithm's termination a globally consistent
layout should be guaranteed.)
-------------------
5. Informational Frames and Gestalts
Anton P. Zeleznikar, An Active Member of the New York Academy of
Sciences, Volariceva ulica 8, SI 1111 Ljubljana, Slovenia, E-mail:
anton.p.zeleznikar@ijs.si
pp. 65-94
Keywords: informational frame-arrangement, concatenation, demarked,
disharmonious, edge syntax, harmonious, operator composition,
parenthesized, possibility, syntax; informational framing;
informational gestalt-axiomatic, causal, circular, inference,
informational machine, intelligent, metaphysicalistic, parallel,
phenomenalistic, reverse, serial, star; informational gestaltism;
number of formulas in a gestalt
Abstract: This article deals with two characteristic and widely useful
notions, called informational frame (of representation) and the
informational gestalt. A preliminary discussion of both notions was
already presented in (17). Informational framing is nothing else than a
part of informational gestaltism by which various causal possibilities
of formulas come into existence. Although a frame is everything which
can be put in a frame within a well-formed informational formula, the
concatenation of framesmust preserve the so-called possibility of a
frame to be a part of a well-formed formula. On the other hand, the
gestalt structure represents a parallel array of informational
formulas, that is, an informational system of causally different
formulas proceeding from a given formula. To this, circular gestalting
can induce the reversely circular properties, so different forms of
gestalts become possible. The most complex and free gestalt called star
gestalt is a consequence of an initial circular formula and its graph,
where operator transitions from one to the next operand are possible in
an arbitrary manner of repeated looping.
-------------------
6. A Distributed Client/Server Benchmark for Network Performance
Measurement
Jozo Dujmovic, Department of Computer Science, San Francisco State
University, 1600 Holloway Avenue, San Francisco, CA 94132, USA, E-mail:
jozo@cs.sfsu.edu AND Robert Kinicki, and Sanjay Subbanna, Department of
Computer Science, Worcester Polytechnic Institute, 100 Institute Road,
Worcester, MA 01609, USA, E-mail: rek@cs.wpi.edu, sanju@cs.wpi.edu
pp. 95-112
Keywords: network benchmarking, network traffic generator, LAN
performance measurement, WAN performance measurement, client/server
pairs
Abstract: We have developed a scalable network traffic generator and a
general computer network benchmark for Unix platforms. This benchmark
can be used to evaluate performance of user-level applications which
interface directly with the transport layer of TCP/IP running on all
types of computer networks. The basic component of the synthetic
network workload is a communicating client/server process pair
performing a cyclic data transfer. The client process repeatedly cycles
through a scenario consisting of an adjustable random wait time
interval, a period where a controllable amount of data is sent to its
server, and a period where the client receives the data back from the
server. The server process receives the data sent by the client, waits
a random time interval, and then transmits the data back to the client
process. The network workload consists of distributed client/server
process pairs (DCSP) and is called the DCSP benchmark. It can include
any number and any distribution of communicating client/server pairs,
yielding a very high level of flexibility and scalability of network
traffic. We propose a standard classification of network workloads,
define network performance indicators, and introduce performance
measurement methods based on various versions of the DCSP benchmark. We
also present experimental results generated using DCSP workloads to
compare LAN configurations, study network saturation phenomena, and
test WAN communications.
-------------------
7. Petri Nets and Self-Stabilization of Communication Protocols
Wuxu Peng, Department of Computer Science, Southwest Texas State
University, San Marcos, TX 78666, U.S.A. AND Kia Makki, Department of
Computer Science, University of Nevada Las Vegas, Las Vegas, Nevada
89154-4019, U.S.A.
pp. 113-124
Keywords: Petri nets, self stabilization, communication protocols
Abstract: Using Petri nets as the concurrent model, we discuss the
issue of self-stabilizing communication protocols in this paper. We
argue that (1) self-stabilizing extensions of communication protocols
should not interfere with their normal operations by giving a new
definition of self-stabilizing extension and a ring net that meets the
new definition, and (2) communication protocols are usually delay
sensitive and time-Petri nets is a more suitable formal model (than
ordinary Petri nets) to express self-stabilizing property. We also
explore the possibility and suitability of using Petri nets with a new
type of transitions - the max transitions - to express self-stabilizing
communication protocols. Finally, to facilitate practical
implementations, two types of interferences - external and internal
interferences - are formally identified and discussed.
-------------------
8. Interface Methods: a Means for the Integration of Inheritance in a
Concurrent OOP Language
Agostino Poggi, Dipartimento di Ingegneria dell'Informazione,
University of Parma, Viale delle Scienze, 43100 Parma, Italy, Phone:
+39 521 90 5728, Fax: +39 521 90 5723, E-mail: poggi@CE.UniPR.IT
pp. 125-134
Keywords: concurrent object-oriented programming languages,
interference between inheritance and concurrency, software reuse
Abstract: Several researchers have pointed out that inheritance often
conflicts with concurrency in object-oriented languages, resulting in
inheritance anomalies where redefinitions of inherited methods are
necessary in order to maintain the integrity of objects. Several
solutions have been proposed for resolving the anomalies; however, some
of them are incomplete and do not solve all the possible types of
inheritance anomalies. Others make the definition of classes complex.
This paper copes with the inheritance anomaly problem presenting a
solution that minimizes the redefinition of inherited methods without
increasing the complexity to write them. This solution is based on the
use of a special set of methods, called interface methods, that divide
their body from two sets of synchronization constraints respectively
used to enable the execution of the body of this method and to disable
the methods that cannot be executed after this method. In particular,
the paper presents a number of examples that illustrate how our
proposal can solve easily the different types of inheritance anomalies.
-------------------
9. The Fringe Bucket-Quadtree, a Robust and Efficient Spatial Data
Structure with a High Population Density
R. Maelbrancke and H. Olivie, K.U.Leuven, Department of Computing
Science, Celestijnenlaan 200A, B3001 Heverlee, Belgium, Phone:
+32-16-327643, Fax: +32-16-327996, E-mail:
rudim,olivie@cs.kuleuven.ac.be
pp. 135-142
Keywords: quadtree, spatial data structures
Abstract: In this paper we present three methods for the augmentation
of population density in bucket oriented quadtrees. These improvement
techniques are incorporated in a new data structure called the Fringe
Bucket-quadtree. Analysis of this structure shows a population density
of 77%.