A complete and recursive feature theory
From MaRDI portal
Publication:673135
Abstract: Various feature descriptions are being employed in logic programming languages and constrained-based grammar formalisms. The common notational primitive of these descriptions are functional attributes called features. The descriptions considered in this paper are the possibly quantified first-order formulae obtained from a signature of binary and unary predicates called features and sorts, respectively. We establish a first-order theory FT by means of three axiom schemes, show its completeness, and construct three elementarily equivalent models. One of the models consists of so-called feature graphs, a data structure common in computational linguistics. The other two models consist of so-called feature trees, a record-like data structure generalizing the trees corresponding to first-order terms. Our completeness proof exhibits a terminating simplification system deciding validity and satisfiability of possibly quantified feature descriptions.
Recommendations
- scientific article; zbMATH DE number 65754
- On completeness theorems for feature logics
- A complete axiomatization of a theory with feature and arity constraints
- scientific article; zbMATH DE number 1222556
- Publication:4942633
- Recursion over realizability structures
- scientific article; zbMATH DE number 3857082
- A rational reconstruction of the domain of feature structures
- General recursion theory. An axiomatic approach
- An Algebra for Features and Feature Composition
Cites work
- scientific article; zbMATH DE number 4053011 (Why is no real title available?)
- scientific article; zbMATH DE number 43017 (Why is no real title available?)
- scientific article; zbMATH DE number 65754 (Why is no real title available?)
- scientific article; zbMATH DE number 67840 (Why is no real title available?)
- A feature constraint system for logic programming with entailment
- An algebraic semantics approach to the effective resolution of type equations
- Feature-constraint logics for unification grammars
- Login: a logic programming language with built-in inheritance
- On the expressivity of feature logics with negation, functional uncertainty, and sort equations
- Records for logic programming
- The Logic of Typed Feature Structures
- The logic of unification in grammar
- Towards a meaning of life
Cited in
(20)- Greatest model semantics for typed feature structures
- Basic theory of feature trees
- Ordering constraints over feature trees expressed in second-order monadic logic.
- Regular path expressions in feature logic
- How to win a game with features
- scientific article; zbMATH DE number 1979744 (Why is no real title available?)
- Combination of constraint systems II: Rational amalgamation
- A new generic scheme for functional logic programming with constraints
- A rational reconstruction of the domain of feature structures
- Logics for unordered trees with data constraints
- How to win a game with features
- Interpreting first-order theories into a logic of records
- Feature automata and recognizable sets of feature trees
- Anti-patterns for rule-based languages
- scientific article; zbMATH DE number 4092797 (Why is no real title available?)
- Theories with the independence property
- A fixed-point semantics for feature type systems
- An improved lower bound for the elementary theories of trees
- scientific article; zbMATH DE number 65754 (Why is no real title available?)
- scientific article; zbMATH DE number 67840 (Why is no real title available?)
This page was built for publication: A complete and recursive feature theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673135)
