Volume 37, Issue 1
  • ISSN 0019-0829
  • E-ISSN: 1783-1490
Buy:$35.00 + Taxes


An extension of completion grammars is being introduced such that the model now deals with prefix, infix, postfix and post-infix word order patterns. It is shown that this extension does not affect the weak generative capacity of the system, which was known to be of type 2.

Also the existing notion of a completion automaton is reworked, mainly to have the distinction in word order be reflected by the operations of the automaton rather than by the transition functions of the underlying finite state machine.

In some recent publications (e.g. Steels (1975), Steels and Vermeir (1976), Steels (1976a&b» we have been dealing with a linguistic model known as compZetion grammars. These grammars were designed to cope with a functional viewpoint on language, this means they deal with case structures for language,expressions, instead of phrase structures as do the well-known Chomsky-type grammars.

The model of completion grammars was developed in a context of research on language processing and automatic translation. In particular it reflects the current tendency to build semantics directed systems, rather than syntax directed ones. (See for a more detailed discussion on the distinction between the two Wilks (1975) and Winograd (1973). For the use of completion grammars in the design of semantics directed systems, we refer to Steels (1975;1976a&b).

What will concern us in this paper is an extension of the model, and a study of the formal properties of these extended systems. Also we will introduce a new class of automata. The paper is organized as follows. First we extend the notion of a completion grammar, we give some intuitive explanations for the extension (1.1.), specify the basic definitions (1.2.) and study its weak generative capacity (1.3.). A second section deals with the automata. Again we start with intuitive explanations (2.1.), give the basic definitions and various examples (2.2.) and finally prove the relation between the grammars and the automata (2.3.).


Article metrics loading...

Loading full text...

Full text loading...


    (1966) Universals in Linguistics. Mouton, Den Haag.
  2. LI, S.
    (1975) (ed.) Word order and word order change. The University of Texas Press, Austin.
  3. MINSKI, M. and S. PAPERT
    (1969) Perceptions. An introduction to computational geometry. The M.I.T. Press, Massachusetts.
  4. SALOMAA, A.
    (1973) Formal languages. Academic Press, New York.
  5. STEELS, L.
    (1975) Completion grammars and their applications. Antwerp Papers in Linguistics, U.I.A., nr. 3.
    [Google Scholar]
  6. (1976a) A formalism for case systems. In: Daniel, L. and M. Brady . Proceedings of the Artificial Intelligence and Simulation of Behavior Summer conference. Edinburg University Press, Edinburgh.
  7. (1976b) Producing natural language from semantic information. Paper presented atthe computational linguistics conference, Ottawa. Antwerp Papers in Linguistics, U.I.A. nr. 6.
    [Google Scholar]
  8. STEELS, L. and D. VERMEIR
    (1976) On the formal properties of completion grammars and their related automata. Antwerp papers in Linguistics, U.I.A., nr. 5.
    [Google Scholar]
  9. (1977) Some results on the relation of word order to grammatical complexity. Forthcoming.
    [Google Scholar]
  10. WILKS, Y.
    (1975) Notes for course on Parsing. Tutorial on computational semantics. Institute for semantics and cognitive studies. Castagnola.
  11. Winograd, T.
    (1973) A survey lecture on Natural Language. Third International Conference on A.I. Stanford.
    [Google Scholar]
  • Article Type: Research Article
This is a required field
Please enter a valid email address
Approval was successful
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error