Spravedlivá výpočetní logika stromu - Fair computational tree logic

Spravedlivá výpočetní logika stromu je konvenční logika výpočetního stromu studoval s výslovnými omezeními spravedlnosti.

Slabá spravedlnost / spravedlnost

Toto deklaruje podmínky, jako jsou všechny procesy prováděné nekonečně často. Pokud považujete procesy za P_i, pak se podmínka stává:

${displaystyle igwedge GFP_ {i}}$

Silná spravedlnost / soucit

Tady, pokud proces vyžaduje zdroj nekonečně často (R), mělo by být umožněno získat zdroj (C) nekonečně často:

${displaystyle igwedge (GFRlongrightarrow GFC)}$

Kontrola modelu pro spravedlivý CTL

Pokud uvažujete o modelu Kripke, spravedlivý model Kripke má sadu států F. Cesta ${displaystyle pi = s_ {o}, s_ {1} tečky}$ je považována za spravedlivou cestu, právě když cesta zahrnuje nekonečně často všechny členy F.
Spravedlivá kontrola modelu CTL omezuje kontroly pouze na spravedlivé cesty. Existují dva druhy:

1. M._F, s_i | = A${displaystyle phi}$ kdyby a jen kdyby ${displaystyle phi}$ drží na VŠECH spravedlivých cestách.

2. M._F, s_i | = E${displaystyle phi}$ kdyby a jen kdyby ${displaystyle phi}$ drží na jedné nebo více spravedlivých cestách.

Spravedlivý stát je stát, ze kterého pochází alespoň jedna spravedlivá cesta. To znamená M_F, s | = EGtrue.

Přístup založený na SCC

The silně připojená součást (SCC) směrovaného grafu je maximálně propojený graf - všechny uzly jsou dosažitelné jeden od druhého. Spravedlivý SCC je ten, který má výhodu v alespoň jednom uzlu pro každou z spravedlivých podmínek.

Chcete-li zkontrolovat spravedlivé EG pro jakýkoli vzorec,

1. Vypočítejte, co se nazývá denotace vzorce. V zásadě všechny stavy takové, že M, s | = vzorec.
2. omezit model na denotaci.
3. Najděte veletrh SCC.
4. Získejte spojení všech 3 (výše).
5. Vypočítejte státy, které se mohou k unii dostat.

Algoritmus Emerson Lei

Charakterizace fixního bodu Exist Globally je dána vztahem: [EGφ] = νZ. ([Φ] ∩ [EXZ]), což je v podstatě limit aplikovaný podle Kleeneovy věty. Pro spravedlivé cesty se stává [Ef Gφ] = νZ. ([Φ] ∩_{Fi ∈FT} [EX [E (Z U (Z ∧ Fi))]), což znamená, že vzorec platí v aktuálním stavu a v následujících stavech a v následujících stavech, dokud nesplní všechny členy spravedlivých podmínek. To znamená, že podmínka je ekvivalentní s jakýmsi přejímacím bodem, kde přijatelnou podmínkou je celá sada spravedlivých podmínek.

Reference

• Emerson, E. A .; Halpern, J. Y. (1985). "Rozhodovací postupy a expresivita v časové logice času větvení". Journal of Computer and System Sciences. 30 (1): 1–24. doi:10.1016/0022-0000(85)90001-7.
• Clarke, E. M .; Emerson, E. A. & Sistla, A. P. (1986). Msgstr "Automatické ověření souběžných systémů v konečném stavu pomocí specifikací časové logiky". Transakce ACM v programovacích jazycích a systémech. 8 (2): 244–263. doi:10.1145/5397.5399.