Zobrazeno 1 - 10
of 6 276
pro vyhledávání: '"EXPTIME"'
Autor:
Hirsch, Robin, McLean, Brett
Publikováno v:
Advances in Modal Logic, Volume 14 (2022) College Publications, 491-506
We prove the EXPTIME-hardness of the validity problem for the basic temporal logic on Minkowski spacetime with more than one space dimension. We prove this result for both the lightspeed-or-slower and the slower-than-light accessibility relations (an
Externí odkaz:
http://arxiv.org/abs/2206.06866
Concrete domains, especially those that allow to compare features with numeric values, have long been recognized as a very desirable extension of description logics (DLs), and significant efforts have been invested into adding them to usual DLs while
Externí odkaz:
http://arxiv.org/abs/2006.02078
Autor:
Bednarczyk, Bartosz
We show that the consistency problem for Statistical EL ontologies, defined by Pe{\~{n}}aloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from
Externí odkaz:
http://arxiv.org/abs/1911.00696
Bertrand et al. [1] (LMCS 2019) describe two-player zero-sum games in which one player tries to achieve a reachability objective in $n$ games (on the same finite arena) simultaneously by broadcasting actions, and where the opponent has full control o
Externí odkaz:
http://arxiv.org/abs/1909.06420
Conference
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
The system of Type PDL ($\tau$PDL) is an extension of Propositional Dynamic Logic (PDL) and its main goal is to provide a formal basis for reasoning about types of actions (modeled by their preconditions and effects) and agent capabilities. The syste
Externí odkaz:
http://arxiv.org/abs/1909.00436
Autor:
Nguyen, Linh Anh
We present the first direct tableau decision procedure with the ExpTime complexity for HPDL (Hybrid Propositional Dynamic Logic). It checks whether a given ABox (a finite set of assertions) in HPDL is satisfiable. Technically, it combines global cach
Externí odkaz:
http://arxiv.org/abs/1705.00848
LTL synthesis -- the construction of a function to satisfy a logical specification formulated in Linear Temporal Logic -- is a 2EXPTIME-complete problem with relevant applications in controller synthesis and a myriad of artificial intelligence applic
Externí odkaz:
http://arxiv.org/abs/1609.04371
Autor:
He, Chaodong, Huang, Mingzhang
We put forward an exponential-time algorithm for deciding branching bisimilarity on normed BPA (Bacis Process Algebra) systems. The decidability of branching (or weak) bisimilarity on normed BPA was once a long standing open problem which was closed
Externí odkaz:
http://arxiv.org/abs/1501.04748
We give the first ExpTime (complexity-optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic SHOQ, which extends the basic description logic ALC with transitive roles, hierarchies of roles, nomina
Externí odkaz:
http://arxiv.org/abs/1405.7221