Zobecněný Büchi automat - Generalized Büchi automaton

v teorie automatů, zobecněný Büchi automat je varianta Büchi automat. Rozdíl oproti Büchi automatu je v jeho přijímací podmínce, tj. Množině stavů. Běh je automatem přijímán, pokud nekonečně často navštěvuje alespoň jeden stav z každé sady podmínky přijetí. Zobecněné automaty Büchi jsou ekvivalentní v expresivní síle s automaty Büchi; je uvedena transformace tady.

v formální ověření, kontrola modelu metoda potřebuje získat automat z a LTL vzorec, který určuje vlastnost programu. Existují algoritmy které překládají a LTL vzorec do zobecněného Büchiho automatu.^[1][2][3][4]pro tento účel. Pojem zobecněný Büchi automat byl zaveden speciálně pro tento překlad.

Formální definice

Formálně je zobecněný automat Büchi n-ticí A = (Q, Σ, Δ,Q₀,${ displaystyle { cal {F}}}$), který se skládá z následujících komponent:

• Q je konečná množina. Prvky Q se nazývají státy z A.
• Σ je konečná množina zvaná abeceda z A.
• Δ:Q × Σ →2^Q je funkce zvaná přechodový vztah z A.
• Q₀ je podmnožinou Q, nazývané počáteční stavy.
• ${ displaystyle { cal {F}}}$ je podmínka přijetí, který je tvořen nula nebo více přijímajících sad. Každá přijímací sada ${ displaystyle F_ {i} in { cal {F}}}$ je podmnožinou Q.

A přijímá přesně ty běhy, ve kterých sada nekonečně často se vyskytujících stavů obsahuje alespoň stav z každé přijímající sady ${ displaystyle F_ {i} in { cal {F}}}$. Všimněte si, že tam může být Ne přijímání sad, v takovém případě jakýkoli nekonečný běh tuto vlastnost triviálně splňuje.

Podrobnější formalismus viz také ω-automat.

Označený generalizovaný automat Büchi

Označený zobecněný Büchi automat je další variantou, ve které je vstup asociován jako štítky se stavy spíše než s přechody. Byl představen Gerthem a spol.^[3]

Formálně je označený generalizovaný automat Büchi n-ticí A = (Q, Σ, L, Δ,Q₀,${ displaystyle { cal {F}}}$), který se skládá z následujících komponent:

• Q je konečná množina. Prvky Q se nazývají státy z A.
• Σ je konečná množina zvaná abeceda z A.
• L: Q → 2^Σ je funkce zvaná funkce označování z A.
• Δ:Q → 2^Q je funkce zvaná přechodový vztah z A.
• Q₀ je podmnožinou Q, nazývané počáteční stavy.
• ${ displaystyle { cal {F}}}$ je podmínka přijetí, který je tvořen nula nebo více přijímajících sad. Každá přijímací sada ${ displaystyle F_ {i} in { cal {F}}}$ je podmnožinou Q.

Nechat w = a₁A₂ ... být ω-slovo nad abecedou Σ. r₁, r₂, ... je běh A na slovo w -li r₁  ∈  Q₀ a pro každého i ≥ 0,r_{i + 1} ∈ Δ (r_i) a A_i ∈ L(r_i).A přijímá přesně ty běhy, ve kterých sada nekonečně často se vyskytujících stavů obsahuje alespoň stav z každé přijímající sady ${ displaystyle F_ {i} in { cal {F}}}$. Všimněte si, že tam může být Ne přijímání sad, v takovém případě jakýkoli nekonečný běh tuto vlastnost triviálně splňuje.

Chcete-li získat verzi bez štítku, štítky se přesunou z uzlů do příchozích přechodů.

Reference