Systém kanálu (počítačová věda) - Channel system (computer science) - Wikipedia

v počítačová věda, a kanálový systém je konečný stavový stroj podobný komunikující konečný stavový stroj ve kterém existuje jeden systém komunikující sám se sebou místo mnoha systémů komunikujících navzájem. A kanálový systém je podobný a zasunovací automat kde se místo fronty použije fronta. Tyto fronty se nazývají kanály. Každý kanál intuitivně představuje posloupnost zprávy, která se má odeslat a číst v pořadí, v jakém se odesílají.

Definice

Systém kanálů

Formálně, a kanálový systém (nebo perfektní kanálový systém) ${ displaystyle S}$ je definován jako n-tice ${ displaystyle langle Q, C, Sigma, Delta rangle}$ s:

${ displaystyle Q = {q_ {1}, tečky, q_ {m} }}$ konečná sada kontrolní stavy,
${ displaystyle q_ {0} v Q}$ an počáteční stav,
${ displaystyle A}$ konečná abeceda (z důvodu jednoduchosti zápisu, ať ${ displaystyle epsilon v A}$ ),
${ displaystyle C = {c_ {1}, tečky, c_ {n} }}$ konečná sada kanály,
${ displaystyle Sigma = {a_ {1}, tečky, a_ {p} }}$ konečná abeceda zprávy,
${ displaystyle Delta subseteq Q krát C krát {?,! } krát Sigma ^ {*} krát A krát Q}$ konečná sada přechodových pravidel s ${ displaystyle Sigma ^ {*}}$ je množina konečných (potenciálně prázdných) slov nad abecedou ${ displaystyle Sigma}$ .^[1]

V závislosti na autorovi, a kanálový systém nemusí mít žádný počáteční stav a může mít prázdnou abecedu.^[2]

Konfigurace

A konfigurace nebo globální stav kanálového systému je a ${ displaystyle n + 1}$ n-tice patřící do ${ displaystyle Q times prod _ {i = 1} ^ {n} ( Sigma ^ {*})}$ . Intuitivně konfigurace ${ displaystyle gamma = (q, w_ {1}, tečky, w_ {m})}$ představuje, že běh je ve stavu ${ displaystyle q}$ a to je ${ displaystyle i}$ -tý kanál obsahuje slovo ${ displaystyle w_ {i}}$ .

Počáteční konfigurace je ${ displaystyle (q_ {0}, epsilon, tečky, epsilon)}$ , s ${ displaystyle epsilon}$ prázdné slovo.

Krok

Intuitivně přechod ${ displaystyle (q, c_ {i},!, u, a, q ')}$ znamená, že systém může přejít do stavu řízení ${ displaystyle q}$ na ${ displaystyle q '}$ napsáním ${ displaystyle u}$ na konec kanálu ${ displaystyle c_ {i}}$ . Podobně ${ displaystyle (q, c_ {i},?, u, a, q ')}$ znamená, že systém může přejít do stavu řízení ${ displaystyle q}$ na ${ displaystyle q '}$ odstraněním a ${ displaystyle u}$ začíná slovo ${ displaystyle c_ {i}}$ .

Formálně vzhledem k konfiguraci ${ displaystyle (q, w_ {1}, tečky, w_ {m})}$ a přechod ${ displaystyle (q, c_ {i},!, u, q ')}$ , je tu dokonalý krok ${ displaystyle (q, w_ {1}, dots, w_ {i-1}, w_ {i}, w_ {i + 1}, dots, w_ {m}) { xrightarrow {a}} _ { mathtt {perf}} (q ', w_ {1}, dots, w_ {i-1}, w_ {i} u, w_ {i + 1}, dots, w_ {m})}$ , kde krok přidá písmeno ${ displaystyle u}$ na konec ${ displaystyle i}$ -th slovo. Podobně, vzhledem k přechodu ${ displaystyle (q, c_ {i},?, u, q ')}$ , je tu dokonalý krok ${ displaystyle (q, w_ {1}, tečky, w_ {i-1}, uw_ {i}, w_ {i + 1}, w_ {m}) { xrightarrow {a}} _ { mathtt { perf}} (q ', w_ {1}, dots, w_ {i-1}, w_ {i}, w_ {i + 1}, dots, w_ {m})}$ kde je první písmeno ${ displaystyle i}$ -th slovo je ${ displaystyle u}$ a byl během kroku odstraněn.

Běh

A perfektní běh je posloupnost dokonalého kroku formy ${ displaystyle gamma _ {0} { xrightarrow {a_ {0}}} _ { mathtt {perf}} gamma _ {1} dots}$ . Nechali jsme ${ displaystyle gamma { xrightarrow [{ mathtt {perf}}] {*}} gamma '}$ naznačují, že je perfektní běh začínající na ${ displaystyle gamma}$ a končí v ${ displaystyle gamma '}$ .

Jazyky

Vzhledem k dokonalému nebo ztrátovému systému kanálu ${ displaystyle S}$ lze definovat více jazyků.

Ještě slovo ${ displaystyle A ^ {*}}$ je přijímán uživatelem ${ displaystyle S}$ pokud se jedná o zřetězení popisků běhu ${ displaystyle S}$ . Jazyk definovaný ${ displaystyle S}$ je sada slov přijímaných uživatelem ${ displaystyle S}$ .

Sada dosažitelné konfigurace ${ displaystyle S}$ , označeno ${ displaystyle R (S)}$ je definována jako sada konfigurace ${ displaystyle gamma}$ dosažitelný z počátečního stavu. Tj. jako soubor konfigurací ${ displaystyle gamma '}$ takhle ${ displaystyle (q_ {0}, epsilon, tečky, epsilon) { xrightarrow {*}} gamma '}$ .

Vzhledem k kanálu ${ displaystyle c}$ , kanál ${ displaystyle c}$ je sada n-tic ${ displaystyle (w_ {1}, tečky w_ {m})}$ takhle ${ displaystyle (c, w_ {1}, tečky, w_ {m}) v R (S)}$ .

Kanálový systém a Turingův stroj

Většina problémů souvisejících s dokonalým kanálovým systémem je nerozhodnutelná^[1]^:92.^[3]^:22 To je způsobeno skutečností, že takový stroj může simulovat běh a Turingův stroj. Tato simulace je nyní načrtnuta.

Vzhledem k tomu, Turingův stroj ${ displaystyle M}$ existuje perfektní systém kanálů ${ displaystyle S}$ takový, že jakýkoli běh ${ displaystyle M}$ délky ${ displaystyle n}$ lze simulovat spuštěním ${ displaystyle S}$ délky ${ displaystyle O (n ^ {2})}$ . Intuitivně tato simulace spočívá jednoduše v tom, že je celá páska simulovaného Turingova stroje v kanálu. Kanál obsahu se poté úplně načte a okamžitě přepíše do kanálu, s jednou výjimkou se změní část obsahu představující hlavu Turingova stroje, aby se simuloval krok výpočtu Turingova stroje.

Varianty

Bylo zavedeno několik variant kanálových systémů. Dvě níže uvedené varianty neumožňují simulovat Turingův stroj a umožňují tak rozhodování o mnoha problémech, které nás zajímají.

Jednokanálový stroj

Jednokanálový stroj je kanálový systém využívající jeden kanál. Stejná definice platí také pro všechny varianty kanálového systému.

Počítadlo

Když abeceda kanálového systému obsahuje jednu zprávu, pak je každý kanál v podstatě počítadlo. Z toho vyplývá, že tyto systémy jsou v zásadě Minské stroje. Říkáme takové systémy pultové stroje. Stejná definice platí pro všechny varianty kanálového systému.^[4]^:337

Kompletně specifikovaný protokol

A zcela specifikovaný protokol (CSP) je definován přesně jako kanálový systém. Pojem krok a běh je však definován odlišně.

CSP připouští dva druhy kroků. Dokonalé kroky, jak jsou definovány výše, a přechod ztráty zprávy krok. Postupně označíme přechod ztráty zprávy ${ displaystyle (q, w_ {1}, tečky, a cdot w_ {i}, tečky, w_ {m}) rightsquigarrow (q, w_ {1}, tečky, w_ {i}, tečky , w_ {m})}$ .

Uvolnění

A ztrátový kanálový systém nebo stroj schopný chyby ztráty je rozšíření zcela specifikovaného protokolu, ve kterém mohou písmena zmizet kdekoli.

Ztrátový kanálový systém připouští dva druhy kroků. Dokonalé kroky, jak jsou definovány výše, a ztrátový krok. Označíme ztrátový krok, ${ displaystyle (q, w_ {1}, tečky, w_ {i} cdot a cdot w '_ {i} tečky ,, w_ {m}) rightsquigarrow (q, w_ {1}, tečky , w_ {i} cdot w '_ {i}, w' _ {m})}$ .

Běh, ve kterém jsou kanály vyprázdněny, jakmile jsou do nich odeslány zprávy, je platný běh podle této definice. Z tohoto důvodu mohou být do těchto systémů zavedeny určité podmínky spravedlnosti.

Spravedlnost kanálu

Dostal zprávu kanál ${ displaystyle c}$ , běh je považován za kanál spravedlivý s ohledem na ${ displaystyle c}$ pokud, za předpokladu, že existuje nekonečně mnoho kroků, ve kterých je zaslán dopis ${ displaystyle c}$ pak existuje nekonečně mnoho kroků, ze kterých se čte dopis ${ displaystyle c}$ . ^[5]^:88

Výpočet se říká, že je kanál spravedlivý, pokud je kanál spravedlivý s ohledem na každý kanál ${ displaystyle c}$ .

Nestrannost

Podmínkou nestrannosti je omezení podmínky spravedlnosti kanálu, ve kterém se zohledňuje kanál i písmeno.

Dostal zprávu ${ displaystyle m}$ a kanál ${ displaystyle c}$ , běh je považován za nestranný s ohledem na ${ displaystyle c}$ a ${ displaystyle m}$ pokud, za předpokladu, že existuje nekonečně mnoho kroků, ve kterých ${ displaystyle m}$ je odeslán na ${ displaystyle c}$ pak existuje nekonečně mnoho kroků, ve kterých ${ displaystyle m}$ se čte z ${ displaystyle c}$ . ^[5]^:83

Výpočet je považován za nestranný s ohledem na kanál ${ displaystyle c}$ pokud je nestranný s ohledem na ${ displaystyle c}$ a zprávy ${ displaystyle m}$ . Říká se, že je nestranný pokud je nestranný s ohledem na všechny kanály ${ displaystyle c}$ .

Spravedlivost zpráv

Vlastnost spravedlnosti zprávy je podobná nestrannosti, ale podmínka musí platit pouze v případě, že existuje nekonečný počet kroků, ve kterých ${ displaystyle m}$ lze číst. Formálně je o běhu řečeno, že jde o zprávu faire ${ displaystyle c}$ a ${ displaystyle m}$ pokud, za předpokladu, že existuje nekonečně mnoho kroků, ve kterých ${ displaystyle m}$ je odeslán na ${ displaystyle c}$ a nekonečně mnoho kroků ${ displaystyle i}$ který se vyskytuje ve stavu ${ displaystyle q}$ takové, že existuje přechod ${ displaystyle (q, m, q ')}$ , pak existuje nekonečně mnoho kroků, ve kterých ${ displaystyle m}$ se čte z ${ displaystyle c}$ . ^[5]^:88

Ohraničenost

Běh má prý omezenou ztrátu, pokud je omezen počet odstraněných písmen mezi dvěma dokonalými kroky.^[4]^:339

Vkládání chyb

A stroj schopný vložit chybu je rozšíření kanálového systému, ve kterém se písmena mohou objevit kdekoli.

Stroj schopný vložit chybu připouští dva druhy kroků. Dokonalé kroky, jak jsou definovány výše, a kroky vložení. Označujeme krok za krokem ${ displaystyle (q, w_ {1}, tečky, w_ {i} cdot w '_ {i} tečky ,, w_ {m}) rightsquigarrow (q, w_ {1}, tečky, w_ { i} cdot a cdot w '_ {i}, w' _ {m})}$ .^[3]^:25

Duplikační chyby

A stroj schopný duplikovat chybu je rozšíření stroje schopného vložit chybu, do kterého je vložené písmeno kopií předchozího písmene.

Stroj schopný vkládat chyby připouští dva druhy kroků. Dokonalé kroky, jak jsou definovány výše, a duplikační kroky. Označujeme krok za krokem ${ displaystyle (q, w_ {1}, tečky, w_ {i} cdot a cdot w '_ {i} tečky ,, w_ {m}) rightsquigarrow (q, w_ {1}, tečky , w_ {i} cdot a cdot a cdot w '_ {i}, w' _ {m})}$ .^[3]^:26

A neduplicitní stroj schopný chyby duplikace je stroj, který zajišťuje, že v každém kanálu se písmena střídají mezi speciálním novým písmenem # a běžným písmenem z abecedy zprávy. Pokud se nejedná o případy, znamená to, že došlo k duplikaci a běh je odmítnut. Tento proces umožňuje zakódovat jakýkoli kanálový systém do stroje schopného chyby duplikace a zároveň jej donutit, aby neměl chyby. Protože kanálové systémy mohou simulovat stroje, z toho vyplývá, že stroje schopné chyby duplikace mohou simulovat Turingův stroj.

Vlastnosti

Sada dostupných konfigurací je rozpoznatelná pro stroje se ztrátovým kanálem^[3]^:23 a stroje schopné vkládat chyby^[3]^:26. Je rekurzivně vyčíslitelný pro stroj schopný chyby duplikace^[3]^:27.

Problémy a jejich složitost

Tato část obsahuje seznam problémů s kanálovým systémem a jejich rozhodovatelnost složitosti nad variantami těchto systémů.

Problém s ukončením

The problém s ukončením spočívá v rozhodování, vzhledem k systému kanálů ${ displaystyle S}$ a počáteční konfigurace ${ displaystyle gamma}$ zda všechny běhy ${ displaystyle S}$ začínající na ${ displaystyle gamma}$ jsou konečné. Tento problém je nerozhodnutelný u systémů s dokonalým kanálem, i když je systém čítačem^[4] nebo když se jedná o jednokanálový stroj^[3]^:26.

Tento problém je rozhodnutelné ale neprimitivní rekurzivní přes ztrátový kanálový systém.^[2]^:10 Tento problém je triviálně rozhodnutelný nad strojem schopným vkládat chyby^[3]^:26.

Problém dosažitelnosti

The dosažitelnost problém spočívá v rozhodování, vzhledem k systému kanálu ${ displaystyle S}$ a dvě počáteční konfigurace ${ displaystyle gamma}$ a ${ displaystyle gamma '}$ zda existuje řada ${ displaystyle S}$ z ${ displaystyle gamma}$ na ${ displaystyle gamma '}$ . Tento problém je nerozhodnutelný u systémů s dokonalým kanálem a rozhodnutelné ale neprimitivní rekurzivní přes ztrátový kanálový systém.^[2]^:10 Tento problém je rozhodnutelný na stroji schopném vkládat chyby.^[3]^:26

Problém dosažitelnosti

The zablokování problém spočívá v rozhodnutí, zda existuje dostupná konfigurace bez následníka. Tento problém je rozhoditelný v systému ztrátových kanálů^[2]^:10 a triviálně rozhodnutelné nad strojem schopným vkládat chyby^[3]^:26. Je také rozhodnutelné přes přepážkový automat.^[6]

Problém s kontrolou modelu

The problém s kontrolou modelu spočívá v rozhodování, zda daný systém ${ displaystyle S}$ a a CTL * * -formula nebo a LTL -vzorec ${ displaystyle phi}$ nebo zda je jazyk definován ${ displaystyle S}$ splňuje ${ displaystyle phi}$ . Tento problém je v systému se ztrátovými kanály nerozhodnutelný.^[3]^:23^[5]

Problém s opakovaným stavem

The opakující se stavový problém spočívá v rozhodování, vzhledem k systému kanálů ${ displaystyle S}$ a počáteční konfigurace ${ displaystyle gamma}$ a stát ${ displaystyle s}$ zda existuje řada ${ displaystyle S}$ , počínaje od ${ displaystyle gamma}$ , procházející nekonečně často státem ${ displaystyle s}$ . Tento problém je v systému se ztrátovými kanály nerozhodnutelný, a to i v případě jediného kanálu.^[3]^:23^[5]^:80

Ekvivalentní konečný stavový stroj

Vzhledem k systému ${ displaystyle S}$ , neexistuje žádný algoritmus, který by počítal a konečný stavový stroj zastupující ${ displaystyle R (S)}$ pro třídu ztrátového kanálového systému.^[3]^:24 Tento problém je rozhodnutelný nad strojem schopným vložit chybu.^[3]^:26

Problém ohraničenosti

The problém omezenosti spočívá v rozhodnutí, zda je sada dosažitelné konfigurace konečná. Tj. délka obsahu každého kanálu je omezena. Tento problém je triviálně rozhodnutelný nad strojem schopným vkládat chyby^[3]^:26. Je také rozhodnutelné přes přepážkový automat.^[6]

Nakonec vlastnosti

The vlastnost eventualitynebo vlastnost nevyhnutelnosti problém spočívá v rozhodování, vzhledem k systému kanálu ${ displaystyle S}$ a sada ${ displaystyle Gamma}$ konfigurací, zda jsou všechny spuštěny ${ displaystyle S}$ začínající na ${ displaystyle gamma}$ prochází konfigurací ${ displaystyle Gamma}$ . Tento problém je nerozhodný pro systém ztrátového kanálu s nestranností^[5]^:84 a se dvěma dalšími omezeními spravedlnosti.^[5]^:87

Bezpečnostní vlastnost

The bezpečnostní majetek problém spočívá v rozhodování, vzhledem k systému kanálu ${ displaystyle S}$ a pravidelná sada ${ displaystyle R}$ zda

Strukturální ukončení

The strukturální ukončení problém spočívá v rozhodování, vzhledem k systému kanálu ${ displaystyle S}$ pokud problém s ukončením platí pro ${ displaystyle S}$ pro každou počáteční konfiguraci. Tento problém je nerozhodnutelný i na přepážkovém automatu.^[4]^:342

Komunikace hierarchického státního stroje

Hierarchické stavové automaty jsou konečné stavové automaty, jejichž stavy samy o sobě mohou být jinými stroji. Protože komunikující konečný stavový stroj je charakterizován souběžností, nejpozoruhodnější vlastností v a komunikující hierarchický stavový stroj je koexistence hierarchie a souběžnosti. To bylo považováno za velmi vhodné, protože to znamená silnější interakci uvnitř stroje.

Ukázalo se však, že koexistence hierarchie a souběžnosti skutečně stojí za zahrnutí jazyka, jazykovou ekvivalenci a veškerou univerzálnost.^[7]

Reference

^ ^A ^b Abdulla, Parosh Aziz; Jonsson, Bengt (1996). Msgstr "Ověření programů s nespolehlivými kanály". Informace a výpočet. 127 (2): 91–101. doi:10.1006 / inco.1996.0053.
^ ^A ^b ^C ^d Schnoebelen, Ph (15. září 2002). "Ověření systémů se ztrátovými kanály má neprprimativní rekurzivní složitost". Dopisy o zpracování informací. 83 (5): 251–261. doi:10.1016 / S0020-0190 (01) 00337-4.
^ ^A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j ^k ^l ^m ⁿ ^Ó Cécé, Gérard; Finkel, Alain (10. ledna 1996). „Nespolehlivé kanály lze snáze ověřit než dokonalé kanály“. Informace a výpočet. 124 (1): 20–31. doi:10.1006 / inco.1996.0003.
^ ^A ^b ^C ^d Mayr, Richard (17. března 2008). Msgstr "Nerozhodnutelné problémy v nespolehlivých výpočtech". Teoretická informatika. 297 (1–3): 337–354. doi:10.1016 / S0304-3975 (02) 00646-1.
^ ^A ^b ^C ^d ^E ^F ^G Abdulla, Parosh Aziz; Jonsson, Bengt (10. října 1996). Msgstr "Nerozhodnutelné problémy s ověřením programů s nespolehlivými kanály". Informace a výpočet. 130 (1): 71–90. doi:10.1006 / inco.1996.0083.
^ ^A ^b Rosier, Louis E .; Gouda, Mohamed G (1983). Rozhodování o pokroku pro třídu komunikujících konečných stavových strojů (zpráva).
^ Alur, Rajeev; Kannan, Sampath; Yannakakis, Mihalis. „Komunikace hierarchických stavových strojů,“ automaty, jazyky a programování. Praha: ICALP, 1999

[decidable-1] A ^b Abdulla, Parosh Aziz; Jonsson, Bengt (1996). Msgstr "Ověření programů s nespolehlivými kanály". Informace a výpočet. 127 (2): 91–101. doi:10.1006 / inco.1996.0053.

[Nonprimitive_recursive-2] A ^b ^C ^d Schnoebelen, Ph (15. září 2002). "Ověření systémů se ztrátovými kanály má neprprimativní rekurzivní složitost". Dopisy o zpracování informací. 83 (5): 251–261. doi:10.1016 / S0020-0190 (01) 00337-4.

[easier-3] A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j ^k ^l ^m ⁿ ^Ó Cécé, Gérard; Finkel, Alain (10. ledna 1996). „Nespolehlivé kanály lze snáze ověřit než dokonalé kanály“. Informace a výpočet. 124 (1): 20–31. doi:10.1006 / inco.1996.0003.

[Counter-4] A ^b ^C ^d Mayr, Richard (17. března 2008). Msgstr "Nerozhodnutelné problémy v nespolehlivých výpočtech". Teoretická informatika. 297 (1–3): 337–354. doi:10.1016 / S0304-3975 (02) 00646-1.

[Undecidable_over_unreliable_channels-5] A ^b ^C ^d ^E ^F ^G Abdulla, Parosh Aziz; Jonsson, Bengt (10. října 1996). Msgstr "Nerozhodnutelné problémy s ověřením programů s nespolehlivými kanály". Informace a výpočet. 130 (1): 71–90. doi:10.1006 / inco.1996.0083.

[Rosier,_Gouda-6] A ^b Rosier, Louis E .; Gouda, Mohamed G (1983). Rozhodování o pokroku pro třídu komunikujících konečných stavových strojů (zpráva).

[7] Alur, Rajeev; Kannan, Sampath; Yannakakis, Mihalis. „Komunikace hierarchických stavových strojů,“ automaty, jazyky a programování. Praha: ICALP, 1999

[1]

[2]

[3]

[4]

[5]

[6]

[7]