Complexidade da lógica modal IK5

8

Qual é a complexidade do problema de satisfação local para a lógica modal ? Aqui, denotamos por a lógica modal sobre quadros euclidianos estendidos com modalidade inversa. Você poderia fornecer alguma referência? Está em ? I K 5 N PEuK5EuK5NP

O que eu sei sobre o tópico?

É fácil ver que o está no , já que há uma redução para (o fragmento guardado de duas variáveis ​​da lógica de primeira ordem) - consulte Decidindo lógicas gramaticais regulares com inversão através da lógica de primeira ordem .E x p T i m e G F 2EuK5ExpTEumeGF2

Por outro lado, o comum é completo.N PK5NP

Podemos escrever uma fórmula equisatisfatável em (o fragmento de uma variável da lógica de primeira ordem), porque os modelos podem ser divididos em três partes: (1) mundo inicial , (2) sucessores de (3) sucessores dos sucessores de . O exemplo de redução para uma lógica ainda mais difícil ( com modalidades classificadas) é descrito em Uma nota sobre a complexidade do problema de satisfação para lógicas modais classificadas . No entanto, na presença de uma modalidade inversa, não podemos fazer o mesmo truque - a breve idéia é que mundos inversos podem exigir o número diferente de sucessores. w w w K 5FO1WWWK5

Bartosz Bednarczyk
fonte

Respostas:

4

A lógica é EXP-completa. Uma maneira de provar o limite inferior é observar que a lógica KTB aumentada com a modalidade universal, ou mesmo apenas a relação global de conseqüências da KTB, é EXP-completa (Chen e Lin [1]; observe que eles indicam KTB como B).

Observe que um quadro IK5 conectado é um único ponto irreflexivo ou consiste em um cluster reflexivo C junto com um conjunto I (possivelmente vazio) de pontos irreflexivos, cada um dos quais vê (em R ) um subconjunto não vazio de C . Assim, R s : = { ( x , y ) C 2 : z I(W,R,R-1)CEuRC é uma relação simétrica em C ; se todo elemento de C é visto por um elemento de I , R s também é reflexivo. Por outro lado, é fácil ver que toda estrutura simétrica reflexiva pode ser obtida dessa maneira. Segue que

Rs: ={(x,y)C2:zEu(R(z,x)R(z,y))}
CCEuRs

KTBvocêϕEuK5-+--ϕ,

onde a tradução comuta com conectivos proposicionais e é definida para operadores modais porϕ

(ϕ)=-(-+ϕ),(UMAϕ)=+ϕ.

Aqui, denota a modalidade universal de K T B U , e + e - denotam respectivamente as modalidades de avanço e retrocesso de IK5.UMAKTBvocê+-

Referência:

[1] Cheng-Chia Chen e I-Peng Lin, A complexidade das teorias modais proposicionais e a complexidade da consistência das teorias modais proposicionais , em: Proc. LFCS 1994 (Anil Nerode e Yu. V. Matiyasevich, orgs.), LNCS 813, Springer, pp. 69-80, doi 10.1007 / 3-540-58140-5_8 .

Emil Jeřábek
fonte
Talvez uma pergunta boba. Tanto quanto eu entendo, você provou que a consequência global em IK5 é pelo menos tão difícil quanto a consequência global em KTB ^ U. Como a satisfação local é um caso especial de problema de conseqüência global, como obtemos dureza para isso?
Bartosz Bednarczyk
1
Não, eu provei que a teorema de idade (que é um caso especial de conseqüência local e global) em IK5 é pelo menos tão difícil quanto a teorema de idade em KTB ^ U. Ou, duplamente, a satisfação em IK5 é tão difícil quanto a satisfação em KTB ^ U. Dito isto, isso realmente não faz nenhuma diferença: conseqüência local e teorematismo têm a mesma complexidade em qualquer lógica modal pelo teorema da dedução, e conseqüência local e global têm a mesma complexidade em qualquer lógica com uma modalidade universal definível (que IK5 possui )
Emil Jerabek
Emil Jeřábek, você está ciente de algum resultado de limite superior para o IK5? Diferentes técnicas, em seguida, traduzindo para GF2, que eu mencionei no meu post?
Bartosz Bednarczyk
1
2O(n)
A última questão. Você poderia me dizer se esse resultado também nos dá algum problema com o problema de satisfação global (não estou familiarizado com o teorema, por isso estou perguntando)? É fácil reduzir a satisfação global à satisfação local se você puder usar a modalidade universal, mas talvez o limite superior do IK5 seja menor que o Exp.
Bartosz Bednarczyk