The Logic-Termal Equivalence is Polynomial-Time Decidable.
Viktor K. SabelfeldPublished in: Inf. Process. Lett. (1980)
Keyphrases
- monadic second order logic
- expressive power
- first order logic
- datalog programs
- truth table
- regular expressions
- special case
- linear time temporal logic
- polynomial hierarchy
- data complexity
- logic programming
- guarded fragment
- query containment
- computational complexity
- query language
- classical logic
- finite automata
- worst case
- nonmonotonic logics
- tree automata
- proof theory
- multi valued
- logical framework
- equivalence relation
- approximation algorithms