Abstract
Feature structures are employed in various forms in many areas of linguistics. Informally, one can picture a feature structure as a sort of tree decorated with information about constraints requiring that specific subtrees be identical (isomorphic). Here I show that this informal picture of feature structures can be used to characterize exactly the class of feature structures under their usual subsumption ordering. Furthermore, once a precise definition of tree is fixed, this characterization makes use only of standard domain-theoretic notions regarding the information borne by elements in a domain, thus removing (or better, explaining) all apparentlyad hoc choices in the original definition of feature structures. In addition, I show how this characterization can be parameterized in order to yield similar characterizations of various different notions of feature structure, including acyclic structures, structures with appropriateness conditions and structures with apartness conditions (used to model path inequations). The generalizations to other notions of feature structure also emphasize that the construction given here is in fact independent of the application to feature structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abramsky, Samson, 1991, “Domain theory in logical form,”Annals of Pure and Applied Logic 51, 1–77.
Aït-Kaci, Hassan and Nasr, Roger, 1986, “LOGIN: A logig programming language with built-in inheritance,”Journal of Logic Programming 3, 185–215.
Aït-Kaci, Hassan and Podelski, A., 1993, “Towards a meaning of LIFE,”Journal of Logic Programming, LNCS vol. 528, 255–274.
Aït-Kaci, Hassan, Podelski, A. and Smolka, Gert, 1994, “A feature-based constraint system for logic programming with entailment,”Theoretical Computer Science 122(1–2), 263–283.
Backofen, Rolf and Smolka, Gert, 1993, “A complete and recursive feature theory,” pp. 193–200 in31st Annual Meeting of the Association for Computational Linguistics, June 1993.
Barwise, Jon, 1991, “Information links in domain theory,” Technical Report IULG-91-7, Indiana University Logic Group.
Blackburn, Patrick, 1994, “Structures, language and translations: The structural approach to feature logics,” pp. 1–27 inConstraints, Language and Computation, M. A. Rosner, C.J. Rupp, and R. L. Johnson, eds., Academic Press.
Carpenter, Robert, 1992,The Logic of Typed Feature Structures. Number 32 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press,
Colmerauer, A., 1984 “Equations and inequations on finite and infinite trees,” pp. 85–99 inProceedings of the International Conference on Fifth Generation Computer Systems.
Kaplan, Ronald and Bresnan, Joan, 1983 “Lexical Functional Grammar: A formal system for grammatical representation,” pp. 173–281 inThe Mental Representation of Grammatical Relations, Joan Bresnan, ed., MIT Press.
Kay, Martin, 1979, “Functional grammar,” pp. 142–158 IiProceedings of the Fifth Annual Metting of the Berkeley Linguistics Society, February 1979.
Mac Lane, Saunders, 1971,Categories for the Working Mathematician, Volume 5 ofGraduate Texts in Mathematics, Springer-Verlag.
Moshier, Michael Andrew, 1988,Extensions to Unification Grammar for the Description of Programming Languages. PhD thesis, University of Michigan.
Paterson, M.S. and Wegman, M.N., 1978, “Linear unification,”Journal of Computer and System Sciences 16, 158–167.
Pereira, Fernando C.N. and Shieber, Stuart M., 1984, “The semantics of grammar formalisms seen as computer languages,” pp. 123–129 inProceedings of the 10th International Conference on Computational Linguistics: COLING 84, July 1984.
Pierce, Benjamin C,1991, Basic Category Theory for Computer Scientists. MIT Press.
Plotkin, Gordon, 1983, “Domains,” University of Edinburgh Lecture Notes.
Pollard, Carl and Sag, Ivan A., 1987,Information-based Syntax and Semantics, Volume 1 ofCSLI Lecture Notes, CSLI.
Smolka, Gert and Treinen, Ralf, 1994, “Records for logic programming,”Journal of Logic Programmingg 18(3), 229–258.
Smyth, Michael, 1983, “The largest cartesian closed category of domains,”Theoretical Computer Science 27(1,2), 109–119.
Vickers, Steven, 1989,Logic via Topology, Volume 5 ofCambridge Tracts in Theoretical Computer Science, Cambridge University Press.
Author information
Authors and Affiliations
Additional information
This research has been supported by the Deutsche Forschungsgemeinschaft as part of Sonderforschungsbereich 314, Projekt N3.
Rights and permissions
About this article
Cite this article
Moshier, M.A. A rational reconstruction of the domain of feature structures. J Logic Lang Inf 4, 111–143 (1995). https://doi.org/10.1007/BF01048617
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01048617