Sökning: WFRF:(Ingólfsdóttir Anna) >
Complexity results ...
Complexity results for modal logic with recursion via translations and tableaux
-
- Aceto, Luca (författare)
- Reykjavik Univ, Dept Comp Sci, Reykjavik, Iceland.;Gran Sasso Sci Inst Aquila, Laquila, Italy.
-
- Achilleos, Antonis (författare)
- Reykjavik Univ, Dept Comp Sci, Reykjavik, Iceland.
-
- Anastasiadi, Elli (författare)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik,Reykjavik Univ, Dept Comp Sci, Reykjavik, Iceland.
-
visa fler...
-
- Francalanza, Adrian (författare)
- Univ Malta, Dept Comp Sci, ICT, Msida, Malta.
-
- Ingolfsdottir, Anna (författare)
- Reykjavik Univ, Dept Comp Sci, Reykjavik, Iceland.
-
visa färre...
-
Reykjavik Univ, Dept Comp Sci, Reykjavik, Iceland;Gran Sasso Sci Inst Aquila, Laquila, Italy. Reykjavik Univ, Dept Comp Sci, Reykjavik, Iceland. (creator_code:org_t)
- LOGICAL METHODS COMPUTER SCIENCE, 2024
- 2024
- Engelska.
-
Ingår i: Logical Methods in Computer Science. - : LOGICAL METHODS COMPUTER SCIENCE. - 1860-5974. ; 30:3
- Relaterad länk:
-
https://doi.org/10.4...
-
visa fler...
-
https://uu.diva-port... (primary) (Raw object)
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
visa färre...
Abstract
Ämnesord
Stäng
- This paper studies the complexity of classical modal logics and of their extension with fixed-point operators, using translations to transfer results across logics. In particular, we show several complexity results for multi-agent logics via translations to and from the mu -calculus and modal logic, which allow us to transfer known upper and lower bounds. We also use these translations to introduce terminating and non-terminating tableau systems for the logics we study, based on Kozen's tableau for the mu -calculus and the one of Fitting and Massacci for modal logic. Finally, we describe these tableaux with mu -calculus formulas, thus reducing the satisfiability of each of these logics to the satisfiability of the mu -calculus, resulting in a general 2EXP upper bound for satisfiability testing.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- NATURVETENSKAP -- Matematik -- Algebra och logik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Algebra and Logic (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas