BUCS Tech Report # 84-001

Natural Language Database Update

Sharon Salveter, Boston University.

February, 1984 (58 pages).


BUCS Tech Report # 84-002

On Simple and Creative Sets in NP

Steven Homer, Boston University.

May, 1984, (22 pages).

Abstract:

Two Structurally defined types of NP sets are studied.  K-simple sets
are defined and shown to exist in NP.  Other properties of these sets are
investigated.  K-creative sets, as previously defined by Joseph and Young,
are next considered. A new condition is given which implies that a set is
k-creative.  Several previously considered NP-complete sets are proved to
be k-creative.


BUCS Tech Report # 85-001

A Computational Theory of Metaphor Comprehension and Analogical Reasoning

Bipin Indurkhya, Boston University.

February 1985, (195 pages).

Abstract:

In this thesis we propose a formal theory of metaphors and analogies.
We start from the assumption that a metaphor, or an analogy, is
characterized by the description of one domain (target domain)
in terms of another domain (source domain).
We describe a formalism, called Schema-Language [SL], for
representing domain knowledge which is based on the First-Order
Predicate Calculus. We then develop a theory of Constrained Semantic
Transference [CST] which shows how the terms and structural
relationships of the source domain can be  coherently transferred to
the target domain. The concept of a T-MAP, which is a partial
coherent mapping from the terms of the source domain to the target
domain, is central to CST.
We show how to characterize metaphors and analogies by using T-MAPs
which can explain many cognitive properties associated with them.
A major limitation of CST is that the
notion of coherency is not computational.

We propose a theory of Approximate Semantic Transference [AST], which
is derived from CST by replacing the coherency requirement on T-MAPs
by approximate coherency. The partial approximate-coherent mappings
of AST, called AT-MAPs, are computational and can be used as a basis
for developing models of cognitive processes involved in
comprehending metaphors and analogies. We propose two alternative
formulations of approximate coherency. Based on one of these
version, we present several algorithms, and principles that can be
used in designing algorithms, for computing AT-MAPs from the
knowledge of the source and target domains.


BUCS Tech Report # 85-002

A Simple Three-Dimensional Real-Time Reliable Cellular Array

Peter Gacs, Boston University.
 
March 1985, (15 pages).

Abstract:

We build a three-dimensional array of unreliable cellular automata that
can simulate a universal Turing machine (more generally, a one-dimensional
universal iterative array) reliably.  This is the first reliable real-time
simulation.  The encoding is simple repetition, and no decoding is 
needed.  The construction is based on Toom's work.


BUCS Tech Report # 85-003

Nonergodic One-Dimensional Media and Reliable Computation (an informal 
overview)

Peter Gacs, Boston University.

March 1985, (11 pages).

Abstract:

We construct a one-dimensional array of cellular automata on
which arbitrarily large computations can be implemented reliably,
even though each automaton at each step makes an error with some
constant probability.  In statistical mechanics, this construction
refutes the "positive probability conjecture", which states that
any one-dimensional infinite particle system with positive transition
probabilities is ergodic, and our approach takes its origin from
Kurdyumov's ideas for this refutation.

Earlier designs for reliable computation were circuits whose intricate
interconnection pattern (arising from the error-correcting organization)
he had to assume to be immune to errors.  In a uniform cellular medium,
the error-correcting organization exists only in "software", therefore
errors threaten to disable it.  The real technical novelty of the
paper is therefore the construction of a 
self-repairing organization.


BUCS Tech Report # 85-004

Every Sequence is Reducible to a Random One

Peter Gacs, Boston University.

March 1985, (5 pages).

Abstract:

Every infinite binary sequence is Turing-reducible to an infinite
sequence which is random in the sense of Martin-L\*:of.


BUCS Tech Report # 85-005

Leonid A. Levin, Boston University.

(1) Average Case Complete Problems, March 1985, (2 pages).

(2) One-Way Functions and Pseudorandom Generators, March 1985, (3 pages).

(3) Computational Complexity of Functions, 1974, (1 page).

Abstracts:

(1)  Many interesting combinatorial problems were found to be 
NP-complete.  Since there is little hope to solve them fast in the worst case,
researchers look for algorithms which are fast just "on average".  This
matter is sensitive to the choice of a particular
NP-complete problem and a probability distribution of its instances.
Some of these tasks were easy and some not.  But one needs a way to
distinguish the "difficult on average" problems.  Such negative results
could not only save "positive" efforts but may also be used in areas
(like cryptography) where hardness of some problems is a frequent assumption.
It is shown below that the Tiling problem with uniform distribution of
instances has no polynomial "on average" algorithm, unless every NP-problem
with every simple probability distribution
has it.  It is interesting to try to prove similar statements for
other NP-problems which resisted so far "average case" attacks.

(2)  One-way are those functions which are easy to compute, but hard to invert
on a non-negligible fraction of instances.  
The existence of such functions with
some additional assumptions was shown to be sufficient for generating perfect
pseudorandom strings [Blum, Micali 82], [Yao 82], [Goldreich, Goldwassar,
Micali 84].  Below, among a few other observations, a weaker assumption about
one-way functions is suggested, which is not only sufficient, but also
necessary for the existence of pseudorandom generators.  

(3)  This is a partial translation from: Complexity of Algorithms and
Computations.  Ed. Kosmidiadi, Maslov, Petri, "Mir", Moscow, 1974, (pp.
174-185).  Preliminary version:  
On Storage Capacity for Algorithms, DAN SSR = Soviet Math. Dokl.  14/5
(1973).


BUCS Tech Report # 85-007

Necessary and Sufficient Conditions for the Universality of Programming 
Formalisms

A.J. Kfoury, Boston University.

May 1985 (62 pages).

Abstract:

Over many familiar datatypes the notion of "computable" coincides
with the notion of "flowchartable".  For example, any partial recursive
function is defined by a flowchart program over the datatype 
(W,=,succ, 0) where succ is the successor operation on
the set W of natural numbers.  It is also known that flowcharts
are not a universal programming formalism over arbitrary datatypes,
in the sense that the notion of "computable" is strictly more
general than the notion of "flowchartable".

In this paper we consider various extensions and restrictions of the
basic formalism of flowcharts, and then for every such formalism, we
characterize the datatypes over which the computable functions are exactly
the functions programmable in this formalism.  We say that
a function is computable over a datatype if it is effective relative
to the primitive operations and relations of the datatype (which are
assumed to be defined everywhere on the domain of the datatype).

Our results are expressed algebraically, putting simple restrictions on
the primitive operations and relations of datatypes.
For example, we prove that the notion of "computable" over an arbitrary
(one-sorted) datatype \fBA coincides with the notion of "definable
by a flowchart program over \fBA with recursive calls" if and only if:

(   k)(   )(   k-tuple a of elements in the domain of A)

[If a generates more than elements then a generates infinitely many elements].

We also prove that the notion of "computable" over an arbitrary
datatype A coincides with the notion of "definable by a flowchart
program over A with counters" if and only if:

(   k)(   )(   k-tuple a of elements in the domain of A)

[Every element at all generated by a can be generated using memory locations].

We prove several other similar results.  In the last section of the
paper, we examine programmability over familiar algebraic structures
(groups, rings, and fields).


BUCS Tech Report # 85-008

Constrained Semantic Transference: A Formal Theory of Metaphors

Bipin Indurkhya, Boston University.

October 1985. (30 pages).

Abstract:

In this paper we propose a formal theory of metaphors called Constrained
Semantic Transference [CST].  We start from the assumptions that metaphors
are characterized by the description of one domain, called the
target domain, in terms of another domain, called the
source domain;  and that a metaphor works by transferring a set
of structural relationships from the source domain to the target domain
coherently.

Starting from these assumptions, we formally define the concept of T-MAPs
which are partial coherent mappings from the source domain to the 
target domain.  We also define two operators, called Augmentation
and Positing Structure that extend a given T-MAP by adding new structure
to the target domain.

We show how T-MAPs can be used to characterize metaphorical interpretations of
a given set of sentences.  This characterization allows several cognitive
features of metaphors to be described in CST.  In particular, our 
characterization used the same criterion for deciding metaphorical truth as
for literal truths.


BUCS Tech Report # 85-009 

Reliable Computation with Cellular Automata

Peter Gacs, Boston University.

July 1985 (72 pages).

Abstract:

We construct a one-dimensional array of cellular automata on which
arbitrarily large computations can be implemented reliably, even though
each automaton at each step makes an error with some
constant probability.  In statistical physics, this construction
leads to the refutation of the "positive probability conjecture",
which states that any one-dimensional infinte particle system with positive
transition probabilities is ergodic, and our approach takes its
origin from Kurdyumov's ideas for this refutation.

To compute reliably with unreliable components, von Neumann proposed Boolean
circuits whose intricate interconnection pattern (arising from error-correcting
organization) he had to assume to be immune to errors.  In a uniform cellular
medium, the error-correcting organization exists only in "software",
therefore errors threaten to disable it.  The real technical novelty of the
paper is therefore the construction of a self-repairing organization.


BUCS Tech Report # 85-010

Minimal Degrees for Polynomial Reducibilities

Steven Homer, Boston University.

September, 1985. (22 pages).

Abstract:

The existence of minimal degrees is investigated for several 
polynomial reducibilities.  It is shown that no set has minimal
degree with respect to polynomial many-one or Turing reducibility.
This extends a result of Ladner [3] where only recursive sets are
considered.  A polynomial reducibility $ <= sub T sup h $ is defined
which is a strengthening of polynomial Turing reducibility, and
whose properties relate to the \fBP = ?\fBNP question.
For this new reducibility a set of minimal degree is constructed
under the assumption that \fBP=\fBNP.  However, the set constructed is
nonrecursive and it is shown that no recursive set is of minimal
$ <= sub T sup h $.


BUCS Tech Report # 85-011

Analyzing Degradation in Performance of Distributed Programs Due to Contention 
for Shared Resources

Bipin Indurkhya, Boston University.

September 1985 (20 pages).

Abstract:

This paper proposes a model for analyzing degradation in performance of
distributed programs due to contention for shared resources.  The model
assumes that the pattern of requests for shared resources is known in advance
for each task and uses several of the techniques developed in connection
with pipelined computers.  By using this model it is possible to analyze the
performance of a distributed program: to determine the maximum number of 
processors that can be gainfully employed in executing the program; and
to design programs that are more suitable to distribution.  Relative overall
performance of two different distributed programs can also be compared.


BUCS Tech Report # 85-012

Approximate Semantic Transference: A Computational Theory of Metaphors and 
Analogies

Bipin Indurkhya, Boston University.

October 1985, (36 pages).

Abstract:

In this paper we start from the assumption that in a metaphor, or an 
analogy, some terms belonging to one domain (source domain) are used
to refer to objects other than their conventional referents belonging
to a possibly different domain (target domain).  We describe
a formalism, which is based on the First Order Predicate Calculus, for
representing knowledge structure associated with a domain and then develop
a theory of Constrained Semantic Transference [CST] which allows the
terms and the structural relationships of the source domain to be
transferred coherently across to the target domain.  We show how
metaphors and analogies can be characterized in CST in such a way that
many of their cognitive properties can be explained.

We then propose a theory of approximate Semantic Transference [AST] which
is a computational version of CST and is derived from it by replacing the
coherency requirement with approximate coherency.  We show how AST can
be used as a basis for designing models of cognitive processes involved
in comprehending metaphors and analogies.


BUCS Tech Report # 85-013

Computational Linguistics Technical Notes

Wieguo Wang, Boston University.

November 1985, (24 pages).

Abstract:

This technical report contains two technical notes on the analysis of the
Kilbury algorithm for parsing ID/LP Grammars which is part of the GPSG 
framework.  In the first one, two implementations of this algorithm are
given, one in C-prolog, on in Interlisp-D.  In the second one, the algorithm
is compared against the Earley-Shieber algorithm on efficiency.


BUCS Tech Report # 85-014

Concurrency Control on Database Indexes: The mU Protocol

Alexandros Biliris, Boston University.

December 1985 (58 pages).

Abstract:

A great deal of the time spent during the database access is attributed to
searching through indexes.  B-trees and its variants became the most widely
used access aids and therefore maximizing concurrency on them is one of the
most contributed factors in the overall degree of concurrency.
This paper presents a deadlock free, structure preserving, locking protocol
that allows a number of independent search, insertion, and deletion processes,
acting concurrently on a B-tree, to operate even when multiple insertions
or deletions are pending.  The protocol makes use of dynamic compatibility 
relations among locks, in which the assignment of a lock at some particular
instance depends not only on the lock type but also on the current status
of the node and the number and; kind of processes acting currently on this
node.  Simple modifications of the locking rules are presented to 
demonstrate the protocol applicability on B-tree like structures such
as compressed trees and R-trees (for spatial searching).


BUCS Tech Report # 85-015

A Model for the Evaluation of Concurrency Control Algorithms on B-trees:  
Experimental Comparison of Four Locking Protocols

Alexandros Biliris, Boston University.

December 1985 (26 pages).

Abstract:

A simulation model for comparing concurrency control methods on B-trees is 
presented.  The locking protocols presented by Bayer and Schkolnick, Kwong
and Wood, and Samadi are implemented and evaluated along with the mU
protocol.  Quantities such as relative system throughput, average number
of active processes, and average number of processes waiting for a lock
assignment per unit of time have been measured.  Parameters to the simulation
system, include the multiprogramming level, node size, query mix, and
whether the tree is stored in main memory, on a single disk, or it is
distributed on a number of different disks in a way that there is no
conflict among I/O operations.

The results of the performance analysis of these protocols indicate that
when the tree is not stored on a single disk, the mU protocol performs
faster than its competitors.  For systems in which all I/O requests
pass through a single disk drive no improvement should be expected using any
concurrent algorithm.  Examining the role of each of the above parameters it
is concluded that, for a given storage model, query mix probably plays the most
significant role in the performance of all the protocols, while 
they significantly affect the mU protocol.

The major assumptions/limitations which underly the simulation model are
reviewed and their influence on the reported is discussed.


BUCS Tech Report # 86-001

The Weak Generative Capacity of Parenthesis-Free Categorial Grammars

Joyce Friedman, Dawai Dai and Weiguo Wang, Boston University.

January 1986, (20 pages).

Abstract:

We study the weak generative capacity of a class of parenthesis-free
categorial grammars derived from those of Ades and Steedman by varying
the set of reduction rules.  With forward cancellation as the only rule,
the grammars are weakly equivalent to context-free grammars.  When a
backward combination rule is added, it is no longer possible to obtain
all the context-free languages.  With suitable restriction of the forward
partial rule, the languages are still context-free and a push-down automaton
can be used for recognition. Using the unrestricted rule of forward partial
combination, a context-sensitive language is obtained.


BUCS Tech Report # 86-002

Square-free and Overlap-free Words

A.J. Kfoury, Boston University.

January 1986, (16 pages).

Abstract:

We first give a characterization of doubly-infinite overlap-free words over
a binary alphabet.  One consequence of this characterization is a proof
for the existence of uncountably many infinite overlap-free words over
a binary alphabet.  Another consequence is a O(n log n)
algorithm to test whether a word of length n over a binary
alphabet is overlap-free.  Although this algorithm is slower than
recently published linear-time algorithms for the same problem, its analysis
allows us to determine a O(n\ue\d) bound, for some
e < 2, for the number of overlap-free words of length n
(tighter than the previously known O(n\ulog 15\d) bound).


BUCS Tech Report # 86-003

Towards an Intelligent Computer Graphics System

Marek Holynski, Brian R. Gardner, Rafail Ostrovsky, Boston University. 

January 1986, (24 pages).

Abstract:

The development of an interactive computer graphics system that ties
the meaning of a picture to its graphic representation is discussed. 
The system utilizes a technique for knowledge representation which is relevant
both for computer graphics and for artificial intelligence.  The description
of relations among picture elements and concepts that are represented by these
elements is provided in the form of a semantic network and expressed
in Lisp.  In order to display knowledge described by semantic networks,
a Lisp graphics package is used.  By integrating these two tools we are able
to analyze, create, and modify graphics from the standpoint of contextual
understanding.

BUCS Tech Report # 86-004

Phonological Analysis for French Dictation: Preliminaries to an Intelligent
Tutoring System

Joyce Friedman and Carol Neidle, Boston University.

April 1986, (17 pages).

Abstract:

A set of programs for the phonological analysis of French dictation
exercises has been written as a preliminary step in the development
of an Intelligent Tutoring System for French.  In this paper, we
describe and illustrate the programs to date and give an overview
of the total system as envisaged.

BUCS Tech Report # 86-005

Categorial and Non-Categorial Languages

Joyce Friedman and Ramarathnam Venkatesan, Boston University.

April 1986, (5 pages).

Abstract:

We study the formal and linguistic properties of a class of parenthesis-free
categorial grammars derived from those of Ades and Steedman by varying the set
of reduction rules.  We characterize the reduction rules capable of
generating context-sensitive languages as those having a partial combination
rule and a combination rule in the reverse direction.  We show  that any
categorial language is a permutation of some context-free language, thus
inheriting properties dependent on symbol counting only.  We compare
some of their properties with other contemporary formalisms.

BUCS Tech Report # 86-006

Logics of Programs with Boolean Memory

Pawel Urzyczyn, Institute of Mathematics, University of Warsaw.

April 1986, (20 pages).

Abstract:

We discuss the computational power of programs with boolean
(propositional) push-down stores and arrays, and the expressive power of 
logics based on these programs.  In particular we show that over unary 
structures, the mentioned logics occur to be equivalent to their
"algebraic" counterparts.

BUCS Tech Report # 86-007

Computational Testing of Linguistic Models in Syntax and Semantics

Joyce Friedman, Boston University.

June 1986.  (28 pages).

Abstract:

The history of computational models of linguistic theories in syntax
and semantics is reviewed.  This paper was prepared for inclusion in
W. Lenders (ed.), Computational Linguistics: An International Handbook
on Computer Oriented Language Research and Applications, to be published
by Walter de Gruyter, Berlin.

BUCS Tech Report # 86-008

Finitely Typed Functional Programs:  Syntax, Semantics and Implementation
(Part I)

A.J. Kfoury, Boston University and P. Urzyczyn, Institute of Mathematics,
University of Warsaw,  

June 1986 (44 pages).  

Abstract:

In this report we study the properties of a rigidly typed functional 
programming language with higher-level functional definitions. Programs
in this language may be seen as higher-level recursive program schemes.
We define an operational semantics based on normal order evaluation (or
call-by-name) and we state the basic ``syntactic'' results for our 
language: the Church-Rosser property, the standardization theorem, and the 
normalization theorem. Further, we define an imperative ``implementation''
of our language, that is we prove that  a language of imperative
programs (whose main features are the call-by-name parameter mechanism,
dynamic scoping with deep binding, and non-assignable nonlocal variables)
is equivalent to our language in  computational power. The present paper
will be continued in its Part II, where we investigate e.g. the decidability
of the halting problem over finite interpretations and other expressiveness
issues for our language.

BUCS Tech Report # 86-009

Concurrent Program Schemes

A.J. Kfoury, Boston University and P. Urzyczyn, Institute of Mathematics, 
University of Warsaw. 

June 1986 (30 pages)

Abstract:

We study the programming formalism FD of "flow-diagrams" to which we 
gradually add various features of concurrency.  The weakest form of 
concurrency is introducted by the construct \fB"and", which is dual to the 
nondeterministic choice \fB"or" and plays a role similar to universal states
in alternating Turing machines.  When a computation reaches an \fBand 
instruction, it splits into two independent computation branches 
(or processes); thus a computation of a program with \fBand's is no longer 
represented by a sequence of states, but by a tree whose nodes are states, and 
converges only if all the pathes in this tree are finite.  Stronger (and more 
realistic) forms of concurrency are obtained when processes are allowed to 
communicate.  Communication may in turn be introduced in several ways; we 
consider communication by channels and communication by messages.

We calibrate the computational power of classes of concurrent programs FD+
B against that of sequential programs, where B is the addition of 
one of the following features: \fB{and}, {and, or}, {and,or,channels}, or 
{\fBand,or, messages}.  We also consider and compare the expressiveness of 
various logics of programs L\da\u(\fBFD+B), each being a first-order 
logic with model operators a applied to programs in \fBFD+B.

BUCS Tech Report # 86-010

Preference-Oriented Graphics Interface

Marek Holynski, Robert Garneau, and Elaine Lewis, Boston University.

July 1986 (15 pages).

Abstract:

This paper presents a progression of experimental work aimed at 
incorporating principles of graphic presentation and preferences of users into 
a computer graphics system.  These standards for effective visual 
representation of data are based on empirically developed criteria.  Several 
different approaches for obtaining these criteria from picture attributes are 
described.  First relevant attributes are tested using a series of pictures 
created with a menu-driven program.  Then representation criteria are developed
by an automatic rule acquisition program in the form of condition-action rules.
These rules can be utilized by an adaptive graphics system that can generate, 
change and refine images interactively.

BUCS Tech Report # 86-011

Honest Polynomial Degrees and P=? NP

Steven Homer, Boston University and Timothy J. Long, Ohio State University. 

September 1986, (23 pages).

Abstract:

We present a relatively simple proof of an earlier result by one of
the authors showing that if nonrecursive sets cannot be minimal for
honest polynomial-time Turing reducibility $ <= sub T sup h $- minimal),
then P $!=$ NP.  As a corollary to our proof, we strengthen Homer's
result by showing, without assuming that \fBP $!=$ \fBNP, that
there are $ <=  sub T sup h $ -minimal sets for all tally sets.

We also consider the converse of Homer's result, proving some evidence
that the nonexistence of $ <= sub T sup h $ -minimal sets may follow from
\fBP $!=$ \fBNP in an interesting way.  Finally we consider
structural and/or computability properties of sets that cannot be $ <= 
sub T sup h $ -minimal.

BUCS Tech Report # 86-012 

Analogies and Metaphors: an Interdisciplinary Perspective

Bipin Indurykha, Boston University.

December, 1986, (25 pages)

Abstract:

This paper surveys the crucial roles played by analogies and metaphors
in numerous individual and social settings. We argue that the ability to 
derive analogies is one of the most fundamental aspects of intelligent 
behavior. Analogies play a crucial role in the form of metaphors in the 
domain of linguistics, and models in the domain of science. Metaphors pervade 
our everyday life and perception, both on an individual basis as well as on a
more grandiose level in the form of religious and social metaphors. Models 
have a significant affect on the growth and development of science. In this 
paper we argue that there are some very basic cognitive mechanisms that 
underlie all these different phenomena which need to be isolated and studied.

BUCS Tech Report # 86-013 

Automatic Rule Derivations for Semantic Query Optimization

Michael Siegel, Boston University.

December 1986, (24 pages).

Abstract:

Semantic query optimization uses knowledge in the form of integrity 
constraints to improve query execution.  Due to the dependency on expert 
knowledge this method of optimization is limited to databases with user 
specified rule sets.  Generally, the set of user-specified rules is fixed, 
therefore this rule set does not change to reflect changes in the database 
usage pattern.  This paper describes a method of automatic rule derivation that
follows both the database usage pattern and changes in database state.  Rules 
are automatically derived from the database for use in semantic query 
optimization.  We describe an object-oriented approach to semantic query 
optimization using derived rules.  Using this approach we present methods for 
automatically selecting and deriving rules, and for monitoring the performance
of the rule set.  Finally, we examine the maintenance of derived rules in the 
presence of updates.  Automatic rule derivation for semantic query optimization
is a promising self-adaptive database optimization technique that combines 
areas of research from both database theory and artificial intelligence.

BUCS Tech Report # 87-001
Peter Gacs, Boston University and John Reif, Harvard University, MIT
A Simple Three-Dimensional Real-Time Reliable Cellular Array      
January 1987 (32 pages)

Abstract:

We build a three-dimensional array of unreliable cellular automata that can
simulate a universal Turing machine (more generally, a one-dimensional
universal iterative array) reliably.  This is the first reliable real-time 
simulations.  The construction is based on Toom's work.

BUCS Tech Report # 87-002
Peter Gacs, Boston University
Self Correcting Two Dimensional Arrays
January 1987 (73 pages)

Abstract:

BUCS Tech Report # 87-003
A.J. Kfoury, Boston University
The Translation of Functional Programs into Tail-Recursive Form (Part I)
January 1987 (45 pages)


BUCS Tech Report # 87-004
Bipin Indurkhya, Boston University
A Reply to David Stove's "Rationality of Induction"
June 1987 (14 pages)

BUCS Tech Report # 87-005
Steven Homer, Boston University and William Gasarch, University of Maryland-
College Park
Recursion-Theoretic Properties of Minimal Honest Polynomial Degrees
June 1987 (32 pages)

BUCS Tech Report # 87-006
Steven Homer and Jie Wang, Boston University.
Absolute Results Concerning One-Way Functions and Their Applications
June 1987 (22 pages)

BUCS Tech Reports # 87-007
Ramarathanam Venkatesan and Leonid Levin, Boston University
Random Instances of a Graph Coloring Problem are Hard
November 1987 (6 pages)

BUCS Tech Report # 87-008
Brian Doyle, Bryant York, Mark Friedman, Boston University.
An Introduction to Forms and Logic
July 1987 (28 pages)

BUCS Tech Report # 87-009
Bryant W. York, Boston University
PBE: Programming by Ear (A Programming Environment for the Visually Handicapped)
September 1987, (13 pages).

Abstract:

Programming by ear (PBE) is a programming support environment for
visually handicapped individuals.  Its primary goal is to support these
individuals in the creation, editing, execution, and debugging of computer
programs.  A fundamental assumption of PBE is that human auditory 
bandwith is not as great as human visual bandwith.  For this reason
it is simply not sufficient to add a speech synthesizer to a standard
programming environment and to vocalize for the blind user everything that
would have been visually presented to the sighted user.   Members of the 
PBE project specifically address the issues of information density in the
design of each of its components.  Our goal is to develop PBE into a total 
programming environment which significantly increases the productivity of
blind programmers.  This report outlines the overall design of PBE and
presents some of the features of many of the initial components.  Companion
reports provide detailed descriptions of each of the components.

BUCS Tech Report # 87-010

Doubly-Periodic Sequences and a Class of Two-Dimensional Codes  
(preliminary version)

Jerry Goldman, DePaul University, and Steven Homer, Boston University.

September 1987, (11 pages)

Abstract:

In this paper we continue our study of doubly-periodic sequences.  It
is shown that the set of doubly-periodic sequences over a finite field
has the structure of a bialgebra and that it factors as the tensor product
of the set of singly periodic sequences with itself.  This result applies
to the well known construction of two-dimensional cyclic product codes using
cyclic ordering yielding an induced coalgebra structure for these codes.


BUCS Tech Report # 87-011

A Survey of Heterogeneous Database Systems

Michael Siegel, Boston University

October 1987, (68 pages).
 
Abstract:

In this paper, we present a survey of the research on heterogeneous
database systems (HDSs).  By definition a heterogeneous database system is
simply a multiple database system where the databases may be of different 
types, such as relational or network.  A heterogeneous database system must
permit the user to access multiple databases and resolve the differences
between the individual databases.  This survey examines a number of 
implementations of heterogeneous systems..


BUCS Tech Report # 87-012

Automatic Rule Derivation Form Semantic 
Query Optimization

Michael Siegel, Boston University

October 1987, (25 pages).
 
Abstract:

Semantic query optimization uses knowledge in the form of integrity 
constraints to improve query execution.  Due to the dependency on expert
knowledge this method of optimization is limited to databases with user
specified rule sets.   Generally, the set of user-specified rules is fixed;
therefore this rule set does not change to reflect changes in the database
usage pattern.  This paper describes a method of automatic rule derivation 
that follows changes to both the database usage pattern and the database
state.  Rules are automatically derived from the database for use in 
semantic query optimization.  Using an object-based formalization, we present
methods for automatically selecting and deriving rules, and for monitoring
the performance of the rule set.  We also show how improvements to the
optimization process can be achieved by the addition of category semantics to
the data model.  Finally, we examine the maintenance of derived rules in the 
presence of updates.


BUCS Tech Report # 87-013

Lecture Notes on Descriptional Complexity and Randomness

Peter Gacs, Boston University

October 1987, (52 pages).
 
Abstract:

Other interests kept me from finishing these notes, dating mainly from 1982.
My goal was the exposition of Algorithmic Information Theory, but I never got
past the discrete model.  Most results presented here are well-known for the 
workers in the area of Kolmogorov Complexity and Randomness.  Without 
diminishing my responsibility, I attribute the general point of view taken
in these notes and the form in which most results are presented here to Leonid
Levin.


BUCS Tech Report # 87-014

PBE-EMACS: An Editor for the PBE Environment

Kenneth H. East, Boston University

December 1987, (30 pages).

Abstract:

This paper describes PBE-Emacs, an Emacs-like editor designed for use by
visually handicapped programmers.  The goal of PBE-Emacs is to provide
visually handicapped programmers with a powerful, yet flexible, editor for
program text.  Emacs was chosen as a starting point because it supports
modes which configure the editor to edit particular types of text (e.g. 
source code in C, LISP, Pascal, etc.), and because it is readily
customizable via user-written mock-lisp functions.  Through PBE-Emacs,
the visually handicapped programmer is able to create and modify
ordinary text as well as programs written in the C programming language.

The paper begins with a discussion of the vocal responses that PBE-Emacs
must issue, the mechanisms that are used to tailor these responses
to the visually handicapped programmer's needs, and the techniques used for
vocalizing text that the visually handicapped programmer is editing.  The
vocalization and manipulation of earmarks which contain information about
the syntax and structure of C program text are discussed.  Descriptions
of representative PBE-Emacs commands are presented.  Finally, the facilities
available for creating and modifying PBE-Emacs commands are introduced.
Appendices provide a brief description of Emacs-like editors, current
PBE-Emacs key bindings, and implementation notes


BUCS Tech Report # 87-015

Object Specialization

Edward Sciore, Boston University

August 1987, (17 pages).

Abstract:

Specialization hierarchies typically are treated as type-level
constructs, which are used to define various inheritance
mechanisms.  In this paper we consider specialization at the level
of objects.  We show that doing so creates a more flexible and
powerful notion of inheritance, by allowing classes to be
non-homogeneous.  Object specialization can also be used to model
multiple versions of an object, implement lexical scope rules, and
provide a "classless", prototype-based language interface to the user.


BUCS Tech Report # 87-016

Operation Specific Locking in B-Trees

Alexandros Biliris, Boston University

August 1987, (12 pages)

Abstract:

B-trees have been used as an access aid for both primary and
secondary indexing for quite some time.  This paper presents a
deadlock free locking mechanism in which different processes make
use of different lock types in order to reach the leaf nodes.  The
compatibility relations among locks on a node, do not exclusively
depend on their type, but also on the node status and the number and
kind of processes acting currently on the node.  As a result, a number
of insertion or deletion processes can operate concurrently on a node.
The paper presents an appropriate recovery strategy in case of
failure, and discusses the protocol modifications that are required
so it can be used in other similar structures such as B\u+\d-trees,
compressed B-trees, and R-trees for spatial searching.


BUCS Tech Report # 88-001
Complete Problems and Strong Polynomial Reducibilities
K. Ganesan and Steven Homer, Boston University
February, 1988 (13  pages)

BUCS Tech Report # 88-002
Automatic Synthesis of Computer Performance Models (A PMA Progress Report) 
Bryant York, Director of the Laboratory for Automatic Programming Synthesis, 
Boston University
February, 1988 (26  pages)

BUCS Tech Report # 88-003
Optimal Combinatorial Power for Multistage Interconnection Networks
Lewis Stiller, Boston University
March 1988, (8 pages)

BUCS Tech Report # 88-004
PBE Help:  A Help System for the PBE Environment
Shubha Chakravarthy, Boston University
April, 1988 (20 pages)

BUCS Tech Report # 88-005
PBE Customizer:  An Expert Aide for Customizing PBE Emacs
Elizabeth Russel, Boston University 
April 1988 (32 pages) 

BUCS Tech Report # 88-006
PBE Synopsizer:  A Synopsis for the PBE Environment
Himanshu S. Sinha, Boston University
June 1988, (21 pages)

BUCS Tech Report # 88-007
PBE Flowcharter: a Flowcharter for the PBE Environment
Yee Kwong Ngeow, Boston University
June 1988 (24 pages)

BUCS Tech Report # 88-008
P-Creative Sets vs. P-Completely Creative Sets (Preliminary Version)
Jie Wang, Boston University
May, 1988 (22 pages)

BUCS Tech Report # 88-009
Metaphor and Cognition
Bipin Indurkhya, Boston University
June 1988 (109 pages)

BUCS Tech Report # 88-010
Neural Networks for Computational Vision: Motion Segmentation and Stereo
Fusion
Jonathan Marshall, Boston University
August 1988 (100 pages)

BUCS Tech Report # 88-011
Oracles For Structural Properties:  The Isomorphism Problem And
Public-Key Cryptography
Steven Homer, Boston University and Alan L. Selman, Northeastern University
August, 1988 (9 pages)

BUCS Tech Report # 88-012
Finitely Typed Functional Programs*  Part II:  Comparisons to Imperative Languages
A.J. Kfoury, Boston University and P. Urzyczyn, University of Warsaw, Poland
August 1988 (31 pages)

BUCS Tech Report # 88-013
Some Open Problems In the Theory of Program Schemes and Dynamic Logics
A.J. Kfoury, A.P. Stolboushkin, P. Urzyczyn
August 1988 (24 pages)

BUCS Tech Report # 88-014
Massively Parallel Retrograde Endgame Analysis
Lewis Stiller, Boston University
October, 1988 (14 pages)

BUCS Tech Report # 88-015
Analysis of an Exclusive Locking Policy By the Method of Ensemble Averaging
Eugene Pinsky, Boston University
October, 1988 (21 pages)

BUCS Tech Report # 88-016
Ensemble Averaging:  A New Approximation Technique in the Performancec
Analysis of Large-Scale Systems
Eugene Pinsky, Boston University
October, 1988 (48 pages)

BUCS Tech Report # 88-017 (see BUCS Tech Report #89-001)
Title: MetaLISP: A Representation Independent Dialect of LISP with Reduction
Semantics (extended abstract)
Name: Robert Muller
February 1989 (18 pages)

BUCS Tech Report # 88-018
Proofs in Three Envelops
Leonid Levin, Boston University
December, 1988 (2 pages)

BUCS Tech Report # 89-001
Name: Robert Muller, Boston University
Title: MetaLISP  (An Extended Abstract)
November 1988 (14 pages)

BUCS Tech Report # 89-002
Name: Robert Muller, Boston University
Title: Eval and Call by Representation in MetaLISP:
A Representation Independent Dialect of LISP with Reduction Semantics
March 1989 (17 pages)

BUCS Tech Report #89-003
Name: Wei-hsing Wang and Eugene Pinsky, Boston University
Title: An Asymptotic Analysis of Complete Sharing Policy
January 1989 (14 pages)

BUCS Tech Report #89-004
Name: Wei-hsing Wang and Eugene Pinsky, Boston University
Title: "Pricing" in a Completely Shared Resource Environment
April 1989 (10 pages)

BUCS Tech Report #89-005
Name: Sveinn Sveinnon, Boston University
Title: A Massively Parallel Numerical Ordinary Differential Equation Solver
June 1989 (34 pages)

BUCS Tech Report #89-006
Name: Wei-hsing Wang and Eugene Pinsky, Boston University
Title: A Heuristic Analysis of "Pricing" and Resource Allocation in Large
Circuit-Switched Networks
June 1989 (12 pages)

BUCS Tech Report #89-008
Name: Ma. Paz V. de Castro, Boston University
Title: PBE Earmarker: An Earmarker for the PBE Environment
August 1989 (20 pages)

BUCS Tech Report #89-009
Name: A. J. Kfoury, J. Tiuryn, P. Urzyczyn, Boston University
Title: An Analysis of ML Typability
October 1989 (31 pages)

BUCS Tech Report #89-010
Name: A.J. Kfoury, J. Tiuryn, Boston University
Title: Type Reconstruction in Finite Rank Fragments of the Second-Order Lambda
-Calculus
October 1989 (30 pages)

BUCS Tech Report #89-011
Name: A.J. Kfoury, J.Tiuryn, P.Urzyczyn, Boston University
Title: The Undecidability of the Semi-Unification Problem
October 1989 (18 pages)

BUCS Tech Report #89-012
Name: Raymond Chong, Boston University
Title: The Graphical Display of Clause Graphs and Their Spectra
October 1989 (29 pages)

BUCS Tech Report #89-013
Name: Bryant York, Boston University
Title: Computers and Persons with Disabilities
October 1989 (12 pages)  

BUCS Tech Report #89-014
Name: Jay Littman, Boston University
Title: The PBE C Tutor
December 1989 (14 pages)

BUCS Tech Report #89-015
Name: Jeffrey Nimeroff, Boston University
Title: Intelligent Error analysis - the IEA system for VAX C
December 1989 (22 pages)

BUCS Tech Report #90-001
Name: Abdelsalam Heddaya, Boston University 
Title: View-based Reconfiguration of Replicated Data 
February 1990 (22 pages)

BUCS Tech Report #90-002
Name: M. A. Cohen, Boston University 
Title: The Stability of Sustained Oscillations in Symmetric 
Cooperative--Competitive Networks 
February 1990 (10 pages)

BUCS Tech Report #90-003
Name: Wayne Snyder, Boston University
Jean Gallier, University of Pennsylvania;
Paliath Narendran, SUNY Albany; 
David Plaisted, University of North Carolina, and
Title: Rigid E-Unification: NP-completeness and Applications to Equational 
Matings   
February 1990 (64 pages)

BUCS Tech Report #90-004
Name: Wayne Snyder, Boston University; Jean Gallier, University of Pennsylvania; 
Paliath Narendran, SUNY-Albany;  and Stan Raatz, Rutgers University, 
Title: Theorem Proving Using Equational Matings and Rigid E-Unification 
February 1990 (62 pages)

BUCS Tech Report #90-005
Name: Wayne Snyder, Boston University and Jean Gallier, University of Pennsylvania 
Title: Designing Unification Procedures using Transformations: A Survey   
February 1990 (54 pages)

BUCS Tech Report #90-006
Name: Wayne Snyder, Boston University; Jean Gallier, University of Pennsylvania; 
Paliath Narendran, SUNY-Albany;  David Plaisted, University of North Carolina; 
and Stan Raatz, Rutgers University
Title: Finding Canonical Rewriting Systems Equivalent to a Finite Set of 
Ground Equations in Polynomial Time 
February 1990 (20 pages)

BUCS Tech Report #90-007
Name: Wayne Snyder, Boston University 
Title: Efficient Ground Completion: A Fast Algorithm for Generating  Reduced 
Ground Rewriting Systems from a Set of Ground Equations 
February 1990 (40 pages)

BUCS Tech Report #90-008
Name: Wayne Snyder, Boston University 
Title: Higher-Order E-Unification 
February 1990 (15 pages)

BUCS Tech Report #90-009
Name: Wayne Snyder, Boston University 
Title: A Note On the Complexity of Simplification Orderings 
February 1990 (9 pages)

BUCS Tech Report #90-010
Name: Wayne Snyder and  Christopher Lynch,  Boston University 
Title: A Note On the Completeness of SLD-resolution 
February 1990 (3 pages)

BUCS Tech Report #90-011
Name: Michael Cohen, Boston University 
Title: The Construction of Arbitrary Stable Dynamics in Non-Linear Neural 
Networks 
February 1990 (60 pages)

BUCS Tech Report #90-012
Name: Steven Homer, Boston University and Alan Selman, Northeastern University 
Title: Complexity Theory: Encyclopedia Article 
February 1990 (0 pages)

BUCS Tech Report #90-013
Name: Steven Homer, Boston University, Harry Buhrman, University of Amsterdam, 
and Leen Torenvliet, University of Amsterdam 
Title: Honest Reductions, Completeness and Nondeterministic Complexity Classes 
February 1990 (22 pages)

BUCS Tech Report #90-014
Name: Wayne Snyder and Christopher Lynch ,Boston University 
Title: An Inference System for Horn Clause Logic with Equality: A Foundation 
for Conditional ER-Unification and for  Logic Programming in the Presence 
of Equality 
February 1990 (50 pages)

BUCS Tech Report #90-015
Name: Robert L. Carter, Boston University 
Title: Parallel Triangulations of Point Sets in 3D 
April 1990 (41 pages)

BUCS Tech Report #90-016
Name: Anastasios C. Kotsikonas, Boston University 
Title: Fire Dynamics Applied to Visual Simulation: The Turbulent Diffuse Fire 
April 1990 (11 pages)

BUCS Tech Report #90-017
Name: Veniamin Daskalakis, Boston University
Title: OR-Star Parallelism: Connection-Graph Parallel Theorem Proving on the 
Connection Machine 
May 1990 (61 pages)

BUCS Tech Report #90-018
Name: Bryant W. York and Jeffry S. Nimeroff, Boston University
Title: Adaptive Surface-Fitting of Laser-Scanned Data
June 1990 (24 pages)

BUCS Tech Report #90-019
Name: Weiguo Wang, Boston University 
Title: A Note on Safe Transmission Schemes for Achieving Agreement on  
Networks of Bounded Degree 
October 1990 (16 pages)

BUCS Tech Report #90-020
Name: Eugene Pinsky,Boston University 
Title: A Thermodynamic Limit Approach to Proving Asymptotics in Some 
Performance Models 
November 1990 (12 pages)

BUCS Tech Report #91-001
Name: Eugene Pinsky,Boston University 
Title: Modeling Hot Spots in Database Systems 
January 1991 (30 pages)

BUCS Tech Report #91-002
Name: Abdelsalam Heddaya, Prakash S. Ramamurthy, and Himanshu Sinha, Boston 
University. 
Title: Transactional Replication for Typed Objects: Preliminary Results of 
Project BURDS 
January 1991 (8 pages)

BUCS Tech Report #91-003
Name: Pawel Urzyczyn, Boston University 
Title: Primitive Recursion with Existential Types 
February 1991 (24 pages)

BUCS Tech Report #91-004
Name: Alex Biliris,Boston University 
Title: The EOS Large Object Manager
April 1991 (20 pages)

BUCS Tech Report #91-005
Name: Steve Homer,Boston University 
Title: Superpolynomial Circuits, Almost Sparse Oracles and the Exponential 
Hierarchy 
May 1991 (14 pages)

BUCS Tech Report #91-006
Name: Peter Gacs,Boston University 
Title: On Playing "Twenty Questions" with a Liar 
May 1991 (10 pages)

BUCS Tech Report #91-007
Name: Peter Gacs,Boston University 
Title: A fast hardware random number generator using Wolfram's cellular 
automaton rule, with interface to the CAM-6 machine 
June 1991 (16 pages)

BUCS Tech Report #91-008
Name: Dorothea Czedik and Sharon Salveter, Boston University 
Title: An Extensible Language for Representing Expert Knowledge 
September 1991 (13 pages)

BUCS Tech Report #91-009
Name: Dorothea Czedik, Boston University 
Title: A Comparison of the Properties and Concepts of Rule-based Languages 
October 1991 (21 pages)

BUCS Tech Report #91-010
Name: Judy Goldsmith and Steven Homer 
Title: Scalability and the Isomorphism Problem 
October 1991 (11 pages)

BUCS Tech Report #91-011
Name: Alexandros Biliris 
Title: The Performance of Three Database Storage Structures for Managing Large 
Objects 
October 1991 (25 pages)

BUCS Tech Report #91-012
Name: Azer Bestavros,Boston University 
Title: Specification and Verification of Real-time Embedded Systems using 
Time-constrained Reactive Automata 
October 1991 (10 pages)

BUCS Tech Report #91-013
Name: Azer Bestavros,Boston University 
Title: Planning for Embedded Systems: A real-time prespective 
October 1991 (8 pages)

BUCS Tech Report #92-001
Name: Wayne Snyder,Boston University 
Title: Basic Paramodulation and Superposition 
March 1992 (45 pages)

BUCS Tech Report #92-002
Name: Scott E. O'Hara,Boston University
Title: Modelling the `Redescription' Process in the Context of Proportional 
Analogies 
March 1992 (83 pages)

BUCS Tech Report #92-003
Name: Robert L. Popp,Boston University
Title: Survey, Implementation and Analysis of Maximum Flow Algorithms 
April 1992 (111 pages)

BUCS Tech Report #92-004
Name: Abdelsalam Heddaya,Boston University 
      Himanshu Sinha,Boston University
Title: Coherence, Non-Coherence and Local Consistency in Distributed Shared 
Memory for Parallel Computing 
May 1992 (20 pages)

BUCS Tech Report #92-005
Name: Bipin Indurkhya,Boston University 
Title: Metaphor as Change of Representation: An Interaction Theory of 
Cognition and Metaphor 
July 1992 (50 pages)

BUCS Tech Report #92-006
Name: Bipin Indurkhya,Boston University 
Title: Predictive Analogy and Cognition 
July 1992 (18 pages)

BUCS Tech Report #92-007
Name: Leonid Levin,Boston University
Title: Computational Complexity of Functions 
July 1992 (4 pages)

BUCS Tech Report #92-008
Name:
Title:


BUCS Tech Report #92-009
Name: Abdelsalam Heddaya and Himanshu Sinha,Boston University
Title: An Overview of Mermera: A System and Formalism for Non-Coherent Distributed Parallel Memory
September 1992 (22 pages)

BUCS Tech Report #92-010
Name: Peter Gacs,Boston University and Anna Gal,University of Chicago
Title: Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates
September 1992 (13 pages)

BUCS Tech Report #92-011
Name: Michael Wymann-Boni,Boston University
Title: Decidability of Fragments of Combinatory Logic I: Proper Combinators of Order One
September 1992 (13 pages)

BUCS Tech Report #92-012
Name: Leonid Levin,Boston University 
Title: Randomness and Non-determinism
September 1992 (2 pages)

BUCS Tech Report #92-013
Name: Abdelsalam Heddaya and Himanshu Sinha,Boston University
Title: An Implementation of Mermera: A Shared Memory System that Mixes Coherence with Non-Coherence
October 1992 (19 pages)

BUCS Tech Report #92-014
Name: Pawel Urzyczyn, Boston University
Title: Type Reconstruction in F_Omega 
October 1992 (39 pages)

BUCS Tech Report #92-015
Name: Jerzy Tiuryn and Mitchell Wand
Title: Type Reconstruction with Recursive Types and Atomic Subtyping
October 1992 (32 pages)

BUCS Tech Report #92-016
Name: Azer Bestavros,Boston University
Title: Speculative Concurrency Control
November 1992 (7 pages)

BUCS Tech Report #92-017
Name: Azer Bestavros and Spyridon Braoudakis,Boston University
Title: A Family of Speculative Concurrency Control Algorithms for Real-Time Databases
November 1992 (21 pages)

BUCS Tech Report #92-018
Name: Azer Bestavros and Natalya Fridman,Boston University
Title: Implementation of a Vectorized and Pipelined DLX Simulator
November 1992 (34 pages)

BUCS Tech Report #92-019
Name: Azer Bestavros,Robert L. Popp,and Devora Reich,Boston University
Title: Compiler for the Real-Time Systems Specification Language CLEOPATRA
November 1992 (18 pages)

BUCS Tech Report #92-020
Name: Azer Bestavros,Boston University
Title: AIDA-based Communication for Distributed Time-critical Applications
December 1992 (6 pages)

BUCS Tech Report #92-021
Name: A.J. Kfoury, S. Ronchi della Rocca, J. Tiuryn, and P. Urzyczyn,Boston University
Title: On the Elimination of Alpha-Conversion in Higher-Order Lambda-Calculi
December 1992