Elamur Research⌕
☰
home / papers / 1988 / Implementing Systemic Classification by Unification

Implementing Systemic Classification by Unification

Paper · 1988 · C. S. Mellish

Summary

Mellish asks whether the inferences licensed by Halliday's system networks (which property combinations entail or exclude others) can be computed with ordinary first-order term unification, the basic operation of logic programming. He first gives the four network connectives a precise logical reading as unary-predicate axioms. These cover choice systems, simultaneous choices, and conjunctive and disjunctive entry conditions. He then defines subsumption relative to those axioms, so the possible descriptions form a lattice. Parsing and generation rely on incremental description refinement, which needs only two operations: conjunction (greatest lower bound) and subsumption tests. The paper therefore looks for structure-preserving mappings from these description spaces into the lattice of Generalised Atomic Formulae (GAF). There, unification builds conjunctions, unification failure signals incompatibility, and the instantiation ordering tests subsumption. A general "brute force" encoding works but requires repeated variables. Without repeated variables, networks with disjunctive entry conditions cannot be faithfully encoded. This gives a principled way to build feature co-occurrence checks directly into unification-based systems.

Key points

  • System network connectives (choice "|", simultaneous "{", conjunctive "}" and disjunctive "]" entry conditions) are translated into first-order axioms, using an "at most one of" (AMO) operator for choice systems.
  • Subsumption is defined relative to the network's axioms, a special case of Buntine's (1986) generalised subsumption. Incremental description refinement (a term from Bobrow and Webber, 1980) reduces to repeated greatest-lower-bound steps starting from "true".
  • In the GAF lattice (Reynolds 1970), unification (Robinson 1965) is the meet operation. Mapping property names to fixed terms lets conjunction, incompatibility, and subsumption checks all run through standard unification.
  • Repetition-free terms (GAFo) always decide compatibility pairwise. Networks containing "]" violate this property: in the paper's example, the set {a1, b2, c} is inconsistent although every pair in it is consistent. Such networks therefore need repeated variables, whereas the portion of Winograd's verb network examined can be encoded componentwise.
  • Compared with related work, Kasper's (1986) FUG translation yields disjunctive functional descriptions, and Gazdar et al.'s repetition-free unification does not preserve global constraints. Mellish instead builds the constraints into the terms. The work was supported by SERC grant GR/D/08876.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of SussexBrighton · United Kingdom22 works · 3,332 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksPsychology · 1,552 worksExperimental and Cognitive Psychology · 870 works

Cite

Cite as C. S. Mellish. 1988. Implementing Systemic Classification by Unification. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{mellish1988implementing,
  title = {{Implementing Systemic Classification by Unification}},
  author = {C. S. Mellish},
  journal = {Computational Linguistics},
  year = {1988},
  url = {https://aclanthology.org/J88-1004/}
}

References

21 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Birkhoff, Garrett. 1963 Lattice Theory. American Mathematical Society. find
  2. Bundy, Alan; Byrd, Lawrence and Mellish, Chris. 1982 Special Purpose, but Domain Independent, Inference Mechanisms. In Steels, Luc and Campbell, John, Eds., Progress in Artificial Intelligence. John Wiley, Chichester, UK: 93-111. find
  3. Buntine, Wray. 1986 Generalised Subsumption and its Applications to Induction and Redundancy. In Steels, Luc and DuBoulay, Ben, Eds., Procs of the Seventh European Conference on Artificial Intelligence. find
  4. Codish, Michael and Shapiro, Ehud. 1986 Compiling OR-Parallelism into AND-Parallelism. In Shapiro, Ehud, Ed., Procs of the Third International Conference on Logic Programming. Springer Verlag. find
  5. Dahl, Veronica. 1977 Un Systeme Deductif d'Interrogation de Banques de Donnes en Espagnol. PhD dissertation, Groupe d'Intelligence Artificielle, University of Marseille-Luminy. find
  6. Gazdar, Gerald; Klein, Ewan;Pullum, Geoffrey and Sag, Ivan. 1985 Generalised Phrase Structure Grammar. Blackwell. find
  7. Gazdar, Gerald; Pullum, Geoffrey; Carpenter, Robert; Klein, Ewan; Hukari, Thomas and Levine, Robert. (to appear) Category Structures. Computational Linguistics. find
  8. Hudson, Richard A. 1971 English Complex Sentences: An Introduction to Systemic Grammar. North Holland. find
  9. Kasper, Robert. 1986 Systemic Grammar and Functional Unification Grammar. In Benson, J. and Greaves, W., Eds., Selected papers from the Twelfth International Systemics Workshop. Ablex, Norwood, NJ, USA. find
  10. Kay, Martin. 1984 Functional Unification Grammar: A Formalism for Machine Translation. In Procs of COLING-84. find
  11. Kress, Gunther, Ed. 1976 Halliday: System and Function in Language. Oxford University Press. find
  12. McCord, Michael C. 1986 Design of a Prolog-based Machine Translation System. In Shapiro, Ehud, Ed., Procs of the Third International Conference on Logic Programming. Springer Verlag. find
  13. Mellish, Chris S. (forthcoming) Version Spaces, Description Spaces and Unification. Research paper, Dept of Artificial Intelligence, University of Edinburgh. find
  14. Patten, Terry A. 1986 Interpreting Systemic Grammar as a Computational Representation: A Problem Solving Approach to Text Generation. PhD thesis, University of Edinburgh. find
  15. Reynolds, John C. 1970 Transformational Systems and the Algebraic Structure of Atomic Formulas. In Meltzer, Bernard and Michie, Donald, Eds., Machine Intelligence 5. Edinburgh University Press. find
  16. Robinson, J. Alan. 1965 A Machine-Oriented Logic Based on the Resolution Principle. JACM 12, 23-41. find
  17. Ueda, Kazunori. 1986 Making Exhaustive Search Programs Deterministic. In Shapiro, Ehud, Ed., Procs of the Third International Conference on Logic Programming. Springer Verlag. find
  18. Warren, David H. D. 1977 Implementing Prolog: Compiling Predicate Logic Programs: Research Reports 39 and 40, Department of Artificial Intelligence, University of Edinburgh. find
  19. Winograd, Terry. 1972 Understanding Natural Language. Academic Press. find
  20. Winograd, Terry. 1983 Language as a Cognitive Process. Volume 1: Syntax. Addison Wesley. find
  21. NOTES Author's current address: Department of Artificial Intelligence, University of Edinburgh, 80 South Bridge, EDINBURGH EH1 1HN, Scotland. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/mellish-1988-implementing-systemic-classification-unification/