A complete and recursive feature theory

DOI10.1016/0304-3975(94)00188-OzbMATH Open0873.68024arXivcmp-lg/9406019MaRDI QIDQ673135FDOQ673135

Authors: Rolf Backofen, Gert Smolka 

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cmp-lg/9406019

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

zbMATH Keywords

constraint-based grammar formalismsfeature descriptionslogic programming languages

Mathematics Subject Classification ID

Logic programming (68N17) Grammars and rewriting systems (68Q42)

Cites Work

• The Logic of Typed Feature Structures
• Title not available (Why is that?)
• Feature-constraint logics for unification grammars
• Records for logic programming
• An algebraic semantics approach to the effective resolution of type equations
• Title not available (Why is that?)
• On the expressivity of feature logics with negation, functional uncertainty, and sort equations
• A feature constraint system for logic programming with entailment
• The logic of unification in grammar
• Login: a logic programming language with built-in inheritance
• Title not available (Why is that?)
• Title not available (Why is that?)
• Towards a meaning of life

Cited In (19)

• Logics for unordered trees with data constraints
• Anti-patterns for rule-based languages
• Title not available (Why is that?)
• How to win a game with features
• Interpreting first-order theories into a logic of records
• A rational reconstruction of the domain of feature structures
• Regular path expressions in feature logic
• Combination of constraint systems II: Rational amalgamation
• A fixed-point semantics for feature type systems
• How to win a game with features
• A new generic scheme for functional logic programming with constraints
• An improved lower bound for the elementary theories of trees
• Theories with the independence property
• Basic theory of feature trees
• Ordering constraints over feature trees expressed in second-order monadic logic.
• Greatest model semantics for typed feature structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)