Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2021

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic

Bruse Florian, Lange Martin, Lozes Etienne

Fundamenta Informaticae

2021

Vol. 178, nr 1/2

1--30

Higher-Order Fixpoint Logic (HFL) is a modal specification language whose expressive power reaches far beyond that of Monadic Second-Order Logic, achieved through an incorporation of a typed λ -calculus into the modal μ -calculus. Its model checking problem on finite transition systems is decidable, albeit of high complexity, namely k -EXPTIME-complete for formulas that use functions of type order at most k > 0. In this paper we present a fragment with a presumably easier model checking problem. We show that so-called tail-recursive formulas of type order k can be model checked in (k − 1)-EXPSPACE, and also give matching lower bounds. This yields generic results for the complexity of bisimulation-invariant non-regular properties, as these can typically be defined in HFL.