CTL * e mu-calculus

9

é bem sabido que o modal -calculusμ é um dos mais expressivos lógicas temporais para expressar propriedades de árvores / gráficos, e que CTL * é estritamente menos expressivo do que o -calculus.μ

Aqui, gostaria de pedir um exemplo da fórmula cálcio, o mais simples possível, que não seja expressável em CTL *, e, esperançosamente, uma explicação sobre seu significado (as fórmulas de ponto fixo rapidamente se tornam ilegíveis). Qualquer boa referência para um exemplo simples "concreto" também seria ótimo!μ

Agradeço antecipadamente

LORE81
fonte

Respostas:

11

Pegue uma propriedade de caminho que não seja expressável de primeira ordem, por exemplo, que diz que existe um caminho em que a proposição atômica p se mantém em todas as posições pares e qualquer avaliação pode ser usada em posições ímpares.

νx.px
p
Sylvain
fonte
muito obrigado por esta resposta simples. Você também pode sugerir uma referência para apoiar este exemplo? Obrigado novamente
LORE81
Boa pergunta e resposta (+2). Dê uma olhada em cstheory.stackexchange.com/q/16186/6424 . Também dei o exemplo da uniformidade. Talvez alguma resposta também se refira à uniformidade.
precisa saber é o seguinte
p