@inproceedings{10.1007/978-3-642-33353-8_10,
    Abstract = {We investigate the complexity of satisfiability for one-agent Refinement Modal Logic ({\$}{\backslash}text{\{}{\backslash}sffamily RML{\}}{\$}), a known extension of basic modal logic ({\$}{\backslash}text{\{}{\backslash}sffamily ML{\}}{\$}) obtained by adding refinement quantifiers on structures. It is known that {\$}{\backslash}text{\{}{\backslash}sffamily RML{\}}{\$}has the same expressiveness as {\$}{\backslash}text{\{}{\backslash}sffamily ML{\}}{\$}, but the translation of {\$}{\backslash}text{\{}{\backslash}sffamily RML{\}}{\$}into {\$}{\backslash}text{\{}{\backslash}sffamily ML{\}}{\$}is of non-elementary complexity, and {\$}{\backslash}text{\{}{\backslash}sffamily RML{\}}{\$}is at least doubly exponentially more succinct than {\$}{\backslash}text{\{}{\backslash}sffamily ML{\}}{\$}. In this paper, we show that {\$}{\backslash}text{\{}{\backslash}sffamily RML{\}}{\$}-satisfiability is `only' singly exponentially harder than {\$}{\backslash}text{\{}{\backslash}sffamily ML{\}}{\$}-satisfiability, the latter being a well-known PSPACE-complete problem. More precisely, we establish that {\$}{\backslash}text{\{}{\backslash}sffamily RML{\}}{\$}-satisfiability is complete for the complexity class AEXP{\$}{\\_}{\{}{\backslash}text{\{}{\backslash}sffamily pol{\}}{\}}{\$}, i.e., the class of problems solvable by alternating Turing machines running in single exponential time but only with a polynomial number of alternations (note that NEXPTIME⊆ AEXP{\$}{\\_}{\{}{\backslash}text{\{}{\backslash}sffamily pol{\}}{\}}{\$}⊆ EXPSPACE).},
    Address = {Berlin, Heidelberg},
    Author = {Bozzelli, Laura and van Ditmarsch, Hans and Pinchinat, Sophie},
    BookTitle = {Logics in Artificial Intelligence},
    Editor = {del Cerro, Luis Fari{\\textasciitilde {n}}as and Herzig, Andreas and Mengin, J{\'e}r{\^o}me},
    File = {The Complexity of One-Agent Refinement Modal Logic - Bozzelli2012\_Chapter\_TheComplexityOfOne-AgentRefine.pdf},
    ISBN = {978-3-642-33353-8},
    Pages = {120--133},
    Publisher = {Springer Berlin Heidelberg},
    Title = {The Complexity of One-Agent Refinement Modal Logic},
    Year = {2012},
    date-added = {2022-01-06 08:19:30 +0100},
    date-modified = {2022-01-06 08:19:30 +0100},
    doi = {10.1007/978-3-642-33353-8_10}
}

@inproceedings{10.1007/978-3-642-33353-8_10, Abstract = {We investigate the complexity of satisfiability for one-agent Refinement Modal Logic ({\$}{\backslash}text{{}{\backslash}sffamily RML{}}{\$}), a known extension of basic modal logic ({\$}{\backslash}text{{}{\backslash}sffamily ML{}}{\$}) obtained by adding refinement quantifiers on structures. It is known that {\$}{\backslash}text{{}{\backslash}sffamily RML{}}{\$}has the same expressiveness as {\$}{\backslash}text{{}{\backslash}sffamily ML{}}{\$}, but the translation of {\$}{\backslash}text{{}{\backslash}sffamily RML{}}{\$}into {\$}{\backslash}text{{}{\backslash}sffamily ML{}}{\$}is of non-elementary complexity, and {\$}{\backslash}text{{}{\backslash}sffamily RML{}}{\$}is at least doubly exponentially more succinct than {\$}{\backslash}text{{}{\backslash}sffamily ML{}}{\$}. In this paper, we show that {\$}{\backslash}text{{}{\backslash}sffamily RML{}}{\$}-satisfiability is `only' singly exponentially harder than {\$}{\backslash}text{{}{\backslash}sffamily ML{}}{\$}-satisfiability, the latter being a well-known PSPACE-complete problem. More precisely, we establish that {\$}{\backslash}text{{}{\backslash}sffamily RML{}}{\$}-satisfiability is complete for the complexity class AEXP{\$}{\}{{}{\backslash}text{{}{\backslash}sffamily pol{}}{}}{\$}, i.e., the class of problems solvable by alternating Turing machines running in single exponential time but only with a polynomial number of alternations (note that NEXPTIME⊆ AEXP{\$}{\}{{}{\backslash}text{{}{\backslash}sffamily pol{}}{}}{\$}⊆ EXPSPACE).}, Address = {Berlin, Heidelberg}, Author = {Bozzelli, Laura and van Ditmarsch, Hans and Pinchinat, Sophie}, BookTitle = {Logics in Artificial Intelligence}, Editor = {del Cerro, Luis Fari{\textasciitilde {n}}as and Herzig, Andreas and Mengin, J{\'e}r{\^o}me}, File = {The Complexity of One-Agent Refinement Modal Logic - Bozzelli2012_Chapter_TheComplexityOfOne-AgentRefine.pdf}, ISBN = {978-3-642-33353-8}, Pages = {120--133}, Publisher = {Springer Berlin Heidelberg}, Title = {The Complexity of One-Agent Refinement Modal Logic}, Year = {2012}, date-added = {2022-01-06 08:19:30 +0100}, date-modified = {2022-01-06 08:19:30 +0100}, doi = {10.1007/978-3-642-33353-8_10} }