EUVIMEDEUVIMED entdecken
Crossref

Basic theory of feature trees

Pawel Mielniczuk

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →