We consider the decision problem for cases of first-order temporal logic with
function symbols and without equality. The monadic monodic fragment with flexible
functions can be decided with EXPSPACE-complete complexity. A single rigid function
is sufficient to make the logic not recursively enumerable. However, the monadic monodic
fragment with rigid functions, where no two distinct terms have variables bound by the
same quantifier, is decidable and EXPSPACE-complete.
History
School
Science
Department
Computer Science
Citation
HUSSAK, W., 2008. Decidable cases of first-order temporal logic with functions. Studia Logica, 88 (2), pp. 247-261
Publication date
2008
Notes
This article is Restricted Access. The definitive version is available at: http://www.springerlink.com/content/0039-3215