model,4-3-P86-1038,bq |
is desirable . We have developed a
<term>
|
model
|
</term>
in which descriptions of
<term>
feature
|
#14674
We have developed amodel in which descriptions of feature structures can be regarded as logical formulas, and interpreted by sets of directed graphs which satisfy them. |
other,0-1-P86-1038,bq |
of the two
<term>
formalisms
</term>
.
<term>
|
Unification-based grammar formalisms
|
</term>
use structures containing sets of
|
#14623
We then turn to a discussion comparing the linguistic expressiveness of the two formalisms.Unification-based grammar formalisms use structures containing sets of features to describe linguistic objects. |
other,1-4-P86-1038,bq |
graphs
</term>
which satisfy them . These
<term>
|
graphs
|
</term>
are , in fact ,
<term>
transition graphs
|
#14700
Thesegraphs are, in fact, transition graphs for a special type of deterministic finite automaton. |
other,1-5-P86-1038,bq |
deterministic finite automaton
</term>
. This
<term>
|
semantics
|
</term>
for
<term>
feature structures
</term>
|
#14718
Thissemantics for feature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified by disjunctions and path values embedded within disjunctions. |
other,1-7-P86-1038,bq |
denotational semantics
</term>
. This
<term>
|
logical model
|
</term>
yields a calculus of
<term>
equivalences
|
#14773
Thislogical model yields a calculus of equivalences, which can be used to simplify formulas. |
other,1-9-P86-1038,bq |
computationally inefficient . Our
<term>
|
model
|
</term>
allows a careful examination of the
|
#14806
Ourmodel allows a careful examination of the computational complexity of unification. |
other,10-10-P86-1038,bq |
</term>
for
<term>
formulas
</term>
with
<term>
|
disjunctive values
|
</term>
is
<term>
NP-complete
</term>
. To deal
|
#14828
We have shown that the consistency problem for formulas withdisjunctive values is NP-complete. |
other,11-1-P86-1038,bq |
of
<term>
features
</term>
to describe
<term>
|
linguistic objects
|
</term>
. Although
<term>
computational algorithms
|
#14634
Unification-based grammar formalisms use structures containing sets of features to describelinguistic objects. |
other,12-6-P86-1038,bq |
of Pereira and Shieber by using a
<term>
|
logical model
|
</term>
in place of a
<term>
denotational semantics
|
#14763
Our interpretation differs from that of Pereira and Shieber by using alogical model in place of a denotational semantics. |
other,13-10-P86-1038,bq |
with
<term>
disjunctive values
</term>
is
<term>
|
NP-complete
|
</term>
. To deal with this
<term>
complexity
|
#14831
We have shown that the consistency problem for formulas with disjunctive values isNP-complete. |
other,15-3-P86-1038,bq |
structures
</term>
can be regarded as
<term>
|
logical formulas
|
</term>
, and interpreted by sets of
<term>
|
#14685
We have developed a model in which descriptions of feature structures can be regarded aslogical formulas, and interpreted by sets of directed graphs which satisfy them. |
other,15-7-P86-1038,bq |
</term>
, which can be used to simplify
<term>
|
formulas
|
</term>
.
<term>
Unification
</term>
is attractive
|
#14787
This logical model yields a calculus of equivalences, which can be used to simplifyformulas. |
other,18-6-P86-1038,bq |
<term>
logical model
</term>
in place of a
<term>
|
denotational semantics
|
</term>
. This
<term>
logical model
</term>
yields
|
#14769
Our interpretation differs from that of Pereira and Shieber by using a logical model in place of adenotational semantics. |
other,21-11-P86-1038,bq |
which delays
<term>
expansion
</term>
to
<term>
|
disjunctive normal form
|
</term>
. This paper describes a domain independent
|
#14854
To deal with this complexity, we describe how disjunctive values can be specified in a way which delays expansion todisjunctive normal form. |
other,23-3-P86-1038,bq |
</term>
, and interpreted by sets of
<term>
|
directed graphs
|
</term>
which satisfy them . These
<term>
graphs
|
#14693
We have developed a model in which descriptions of feature structures can be regarded as logical formulas, and interpreted by sets ofdirected graphs which satisfy them. |
other,26-5-P86-1038,bq |
for values which are specified by
<term>
|
disjunctions
|
</term>
and
<term>
path values
</term>
embedded
|
#14743
This semantics for feature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified bydisjunctions and path values embedded within disjunctions. |
other,28-2-P86-1038,bq |
and a more precise description of
<term>
|
feature structures
|
</term>
is desirable . We have developed
|
#14665
Although computational algorithms for unification of feature structures have been worked out in experimental research, these algorithms become quite complicated, and a more precise description offeature structures is desirable. |
other,28-5-P86-1038,bq |
specified by
<term>
disjunctions
</term>
and
<term>
|
path values
|
</term>
embedded within
<term>
disjunctions
|
#14745
This semantics for feature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified by disjunctions andpath values embedded within disjunctions. |
other,3-5-P86-1038,bq |
</term>
. This
<term>
semantics
</term>
for
<term>
|
feature structures
|
</term>
extends the ideas of Pereira and
|
#14720
This semantics forfeature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified by disjunctions and path values embedded within disjunctions. |
other,32-5-P86-1038,bq |
<term>
path values
</term>
embedded within
<term>
|
disjunctions
|
</term>
. Our interpretation differs from
|
#14749
This semantics for feature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified by disjunctions and path values embedded withindisjunctions. |