Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

EXPSPACE-Complete Variant of Guarded Fragment with Transitivity
(Extended Abstract)

Emanuel KierońskiContact Information

(6)  Institute of Computer Science, University of Wrocław, Wrocław
Abstract
We introduce a new fragment GF 2 + $$
\overrightarrow {TG} 
$$ of the first order logic — the two-variable guarded fragment with one-way transitive guards. This logic corresponds in a natural way to temporal logics without past operators. We prove that the satisfiability problem for GF+ $$
\overrightarrow {TG} 
$$ is EXPSPACE-complete. The lower bound, obtained for the monadic version of the considered logic without equality, improves NEXPTIME lower bound for the whole two-variable guarded fragment with transitive guards GF 2 + TG, given by Szwast and Tendera [8].
Supported by KBN grant 8 T11C 043 19

Contact Information Emanuel Kieroński
Email: kiero@ii.uni.wroc.pl
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb22
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)