We develop a matching algorithm for an equational theory with multiplication, exponentiation and a unit element. The algorithm is proved consistent, complete and minimal using techniques based on initial algebras.

The work presented here attempts to bring out some fundamental concepts that underlie some known parsing algorithms, usually called chart or dynamic programming parsers, in the hope of guiding the design of similar algorithms for other formalisms that could be considered for describing the “surface” syntax of languages. The key idea is that chart parsing is essentially equivalent to a simple construction of the intersection of the language (represented by its grammar) with a regular set containing only the input sentence to be parsed (represented by a finite state machine). The resulting grammar for that intersection is precisely what is usually called a shared forest: it represents all parses of a syntactically ambiguous sentence. Since most techniques for processing ill‐formed input can be modeled by considering a nonsingleton regular set of input sentences, we can expect to generalize these ill‐formed input processing techniques to all parsers describable with our approach.

Distributed symbolic computations involve the existence of remote references allowing an object, local to a processor, to designate another object located on another processor. To reclaim inaccessible objects is the non trivial task of a distributed Garbage Collector (GC). We present in this paper a new distributed GC algorithm which (i) is fault-tolerant, (ii) is largely independent of how a processor garbage collects its own data space, (iii) does not need centralized control nor global stop-the-world synchronization, (iv) allows for multiple concurrent active GCs, (v) does not require to migrate objects from processor to processor and (vi) eventually reclaims all inaccessible objects including distributed cycles.

The Context-Free backbone of some natural language analyzers produces all possible CF parses as some kind of shared forest, from which a single tree is to be chosen by a disambiguation process that may be based on the finer features of the language. We study the structure of these forests with respect to optimality of sharing, and in relation with the parsing schema used to produce them. In addition to a theoretical and experimental framework for studying these issues, the main results presented are:- sophistication in chart parsing schemata (e.g. use of look-ahed) may reduce time and space efficiency instead of improving it,- there is a shared forest structure with at most cubic size for any CF grammar,- when O(n3) complexity is required, the shape of a shared forest is dependent on the parsing schema used.Though analyzed on CF grammars for simplicity, these results extend to more complex formalisms such as unification based grammars.

We use the concept of evaluation up to a given threshold of information to generalize the semantics of call by value and assignment to non-discrete domains, and to define a formal semantics for generic procedures. We then prove the correctness of McCarthy's transformation of iterative programs into recursive ones provided the same threshold is used for assignment and parameter passing.