Dynamic Interpretations of Constraint-Based Grammar

Formalisms

Lawrence S. Moss
Mathematics and Computer Science Departments, Indiana University, Bloomington, IN 47405 USA.

and

David E. Johnson
Mathematical Sciences Department, Thomas J. Watson Research Center, IBM Research Division, Yorktown Heights, NY 10598 USA.

March 10, 1995

Abstract. We present a rendering of some common grammatical formalisms in terms of evolving algebras. Though our main concern in this paper is on constraint-based formalisms, we also discuss the more basic case of context-free grammars. Our aim throughout is to highlight the use of evolving algebras as a specification tool to obtain grammar formalisms.

Key words: Constraint-based formalism, evolving algebra

1. Introduction

The main point of this paper is to explore the use of evolving algebra methods in the specification of grammar formalisms. The subject of evolving algebras was introduced by Yuri Gurevich around 1985 as a means of specifying various operational aspects of computation. It provides a clear and uniform way to specify algorithms, programs, programming languages, operating systems, circuitry, etc., often at a level of detail appropriate for reasoning about the system in question. It is unashamedly operational, and yet the mathematical models produced abstract away from details such as machine execution.

The claimed advantages of using evolving algebra methods are chiefly those associated with specification: by having clear specifications, people can use, test, modify a system, as well as teach it to others. On the other hand, the EA work is not an attempt to answer some of the questions which drive the declarative or denotational approaches to semantics, such as providing mathematical models for difficult features of computation, or giving foundations for program equivalence. The evolving algebra framework does seem to provide some general tools for useful specification, and we believe that these tools might be fruitfully applied in linguistics as well.

We feel that some current grammar formalisms are dynamic, on an intuitive level at least. This means that one thinks of some model changing in time as some sort of linguistic data is processed. However, there is a strong tendency to hide the dynamic features of these formalisms and to concentrate on declarative