Abstrakt. P-kalculus kan ses som i huvudsak den "ultimata" programlogiken, eftersom den uttrycksfullt subsumerar alla propositionella programlogiker, inklusive dynamiska logiker, processlogik och temporallogik. Det är känt att tillfredsställande problem för p-calculus är EXPTimefullständig. Denna övre gräns är dock känd för en version av logiken som endast har framåtvända metoder, som uttrycker svagaste förutsättningar, men inte bakåtvända metoder, som uttrycker starkaste postvillkor. Vårt huvudsakliga resultat i detta dokument är en exponentiell tid övre gräns för tillfredsställande problem p-kalculus med både framåt och bakåt villkor. För att få detta resultat utvecklar vi en teori om tvåvägs växelautomat på oändliga träd.
Det satisfiability problemet för den allmänna μ-calculus med omvänt villkor (MC) är känt för att vara EXPTIM-fullständig REF ].
Reasoning about The Past with Two-Way Automata
{'venue': 'In 25th International Colloqium on Automata, Languages and Programming, ICALP ’98', 'journal': None, 'mag_field_of_study': ['Computer Science']}