Basic theory of feature trees
ACM Transactions on Computational Logic · 2004
DOI: 10.1145/1013560.1013561 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, 2004. Verfasst von Pawel Mielniczuk. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 13 Literaturangaben.
Abstract (Originalsprache)
We present a decision algorithm for the problem Val ( FT ) of deciding validity of first-order sentences in the theory of feature trees. Its time complexity is exp ⌊c·m⌋ ( c · n ) where n is the length of a sentence, m is the quantifier depth of a sequence, and c is a constant. The function exp i ( j ) is an exponential tower of 2's of height i , to power j (exp 0 ( j ) = j and exp i +1 ( j ) = 2 exp i ( j ) ). Moreover we prove that the presented algorithm is optimal, deriving a lower bound which matches the upper one.
Zitieren
APA
Mielniczuk, P. (2004). Basic theory of feature trees. ACM Transactions on Computational Logic. https://doi.org/10.1145/1013560.1013561
Vancouver
Mielniczuk P. Basic theory of feature trees. ACM Transactions on Computational Logic. 2004. doi:10.1145/1013560.1013561
BibTeX
@article{Mielniczuk2004,
author = {Mielniczuk, Pawel},
title = {Basic theory of feature trees},
journal = {ACM Transactions on Computational Logic},
year = {2004},
doi = {10.1145/1013560.1013561}
}
EUVIMED