Súlyozott automata
Az elméleti számítástechnikában és különösen az automata elméletben a súlyozott véges automata a véges automaták általánosítása . Egy szokásos véges automatában, legyen az determinisztikus vagy nem-determinisztikus , az átmenetek vagy a nyilak olyan címkéket tartalmaznak, amelyek az alapul szolgáló ábécé betűi. Súlyozott automatában minden átmenet bizonyos súlyt is hordoz. Ezt a súlyt úgy lehet értelmezni, mint az átálláskor az egyik állapotból a másikba való elmozdulás költsége.
Matematikai meghatározás
Hagy egy fél-gyűrű , és hagyja, hogy legyen egy ábécé .
K{\ displaystyle K}Σ{\ displaystyle \ Sigma}
A súlyozott in súlyú automata a következő objektumokból áll:
K{\ displaystyle K}
- egy véges halmaza állapotokQ{\ displaystyle Q}
- átmeneti függvény értékekkel ,μ:Q×Σ×Q→K{\ displaystyle \ mu: Q \ szor \ Sigma \ szoroz Q & K-ig}K{\ displaystyle K}
- bemeneti súlyfüggvény ,λ:Q→K{\ displaystyle \ lambda: Q \ - K}
- egy kimeneti súlyfüggvény .θ:Q→K{\ displaystyle \ theta: Q \ K-ig}
A súlyozott automatákban egy útvonal egy szekvencia
(q0,nál nél1,q1,nál nél2,...,nál nélnem,qnem) {\ displaystyle (q_ {0}, a_ {1}, q_ {1}, a_ {2}, \ ldots, a_ {n}, q_ {n}) \},
hol vannak állapotok és betűk. A szó a címkét az utat, és az elem a félig gyűrű a súlya . A súly tehát az első állapot bemeneti tömegének az átmenetek súlyának szorzatának szorzata, szorozva az utolsó állapot kimeneti tömegével. A tömeg egy szó a automatának az összege a súlyok az összes utakat jelölt . A PLC által kiszámított függvény az a függvény, amely a súlyát egy szóhoz társítja. Hivatalos sorozat formájában is meg van írva:
q0,...,qnem∈Q{\ displaystyle q_ {0}, \ ldots, q_ {n} \ Q-ban}nál nél1,...,nál nélnem∈Σ{\ displaystyle a_ {1}, \ ldots, a_ {n} \ in \ Sigma}nál nél1nál nél2⋯nál nélnem {\ displaystyle a_ {1} a_ {2} \ cdots a_ {n} \}λ(q0)μ(q0,nál nél1,q1)⋯μ(qnem-1,nál nélnem,qnem)θ(qnem){\ displaystyle \ lambda (q_ {0}) \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n} ) \ theta (q_ {n})} w=nál nél1nál nél2...nál nélnem∈Σ∗{\ displaystyle w = a_ {1} a_ {2} ... a_ {n} \ in \ Sigma ^ {*}}π(w){\ displaystyle \ pi (w)}w{\ displaystyle w}
∑w∈Σ∗π(w)w{\ displaystyle \ sum _ {w \ in \ Sigma ^ {*}} \ pi (w) \, w}.
Mátrix jelölés
A súlyozott automata által kiszámított függvényt egyszerűen mátrix jelöléssel fejezzük ki. Ehhez úgy tekintjük, hogy az állapotok halmaza egész számok 1-től . Az átmeneti függvény bármely betű esetében meghatározza a rend szerinti
mátrixotQ={1,...,nem}{\ displaystyle Q = \ {1, \ ldots, n \}}nem{\ displaystyle n}nál nél{\ displaystyle a}v(nál nél){\ displaystyle \ nu (a)}nem{\ displaystyle n}
v(nál nél)o,q=μ(o,nál nél,q){\ displaystyle \ nu (a) _ {p, q} = \ mu (p, a, q)}.
Az n nagyságrendű mátrixok morfizmusára kiterjesztünk a képlettel
v{\ displaystyle \ nu}Σ∗{\ displaystyle \ Sigma ^ {*}}
v(nál nél1nál nél2⋯nál nélnem)=v(nál nél1)v(nál nél2)⋯v(nál nélnem){\ displaystyle \ nu (a_ {1} a_ {2} \ cdots a_ {n}) = \ nu (a_ {1}) \ nu (a_ {2}) \ cdots \ nu (a_ {n})}.
Sorvektornak és oszlopvektornak tekintve a szó súlya ekkor egyszerűen
λ{\ displaystyle \ lambda}θ{\ displaystyle \ theta}w{\ displaystyle w}
π(w)=λv(w)θ{\ displaystyle \ pi (w) = \ lambda \ nu (w) \ theta}.
Ezért találjuk meg a súlyozott automata definícióját is triplettként .
(λ,v,θ){\ displaystyle (\ lambda, \ nu, \ theta)}
Az első példa
A szemben lévő automatának két állapota van. Ez egy automata az egész számok gyűrűjén . A grafikus ábrázolás azt jelzi, hogy a bemeneti vektor az , az átültetett kimeneti vektor az , és a két átmeneti mátrix:
Z{\ displaystyle \ mathbb {Z}}λ=(1 0){\ displaystyle \ lambda = (1 \ 0)}θt=(0 1){\ displaystyle \ theta ^ {t} = (0 \ 1)}
v(nál nél)=(1101){\ displaystyle \ nu (a) = {\ kezdés {pmatrix} 1 & 1 \\ 0 & 1 \ end {pmatrix}}} és
v(b)=(1-101){\ displaystyle \ nu (b) = {\ kezdés {pmatrix} 1 & -1 \\ 0 és 1 \ end {pmatrix}}}
A mátrix számítás azt mutatja, hogy egy szót alkotják betűk és betűk , van
w{\ displaystyle w}o{\ displaystyle p}nál nél{\ displaystyle a}q{\ displaystyle q}b{\ displaystyle b}
v(w)=(1o-q01){\ displaystyle \ nu (w) = {\ kezdete {pmatrix} 1 & p-q \\ 0 és 1 \ end {pmatrix}}}.
A bemeneti és kimeneti vektorok index (1,2) együtthatóval válogatnak, és így meg is van
π(w)=o-q{\ displaystyle \ pi (w) = pq}Szó alkotják betűk és betűk . A nulla súlyú szavak tehát olyan szavak, amelyekből annyi van, mint a . Formális nyelvként ez a nyelv, csakúgy, mint annak kiegészítése, nem szokásos nyelv. Ez azt mutatja, hogy a súlyozott automaták sokkal általánosabb objektumokat ismernek fel.
w{\ displaystyle w}o{\ displaystyle p}nál nél{\ displaystyle a}q{\ displaystyle q}b{\ displaystyle b}nál nél{\ displaystyle a}b{\ displaystyle b}
Egyéb példák
Fél Boole gyűrű . A legegyszerűbb eset a logikai félgyűrű, amely 0-ból és 1 -ből áll. A kifejezés szokásos értelmében vett véges automata súlyozott automatának tekinthető, amelynek értéke in . Ehhez javítjuk:
B{\ displaystyle B}B{\ displaystyle B}
- egy állapot bemeneti súlya 1, ha kezdeti, 0 egyébként,
- egy triplett (p, a, q) súlya 1 vagy 0 attól függően, hogy az automata átmenete-e vagy sem,
- egy állapot kimeneti tömege 1, ha végleges, különben 0.
Ezzel a megfeleléssel a súlyozott PLC útvonal súlya pontosan 1, amikor az út a hagyományos PLC-ben sikeres út, és egyébként 0, és egy szó súlya 1 vagy 0, attól függően, hogy elfogadja-e vagy sem. gép.
Trópusi félgyűrű . Egy másik gyakran fontolóra vett példa a trópusi félgyűrű , ahol az összeadás semleges eleme és 0 a művelet semleges eleme + a szorzás szerepét tölti be. Ennél a súlyozásnál egy út súlya a címkék súlyainak összege, és egy szó súlya az adott szóval címkézett összes út tömegének legkisebb súlya.
T=(R∪∞,min,+,∞,0){\ displaystyle {\ mathcal {T}} = (\ mathbb {R} \ csésze \ infty, \ perc, +, \ infty, 0)}∞{\ displaystyle \ infty}min{\ displaystyle \ min}
Valószínűségi automaták és kvantum automaták . Súlyozott automaták is. Valószínűségi automatában a súlyok valószínűségeket képviselnek, és az ábrázolás mátrixainak sztochasztikusaknak kell lenniük, egy kvantum automatában a mátrixok egységesek .
A Mealy automaták és általában a kész átalakítók súlyozott automatáknak is tekinthetők. A súlyok ekkor az automaták által előállított szavak: pontosabban, ha a kimeneti ábécé, akkor az unióval és az összefűzéssel ellátott részek halmaza félgyűrű. Ezután egy szó súlya képződik az adott címke összes útjának kimeneti szavainak halmazából.
Δ{\ displaystyle \ Delta}Δ∗{\ displaystyle \ Delta ^ {*}}
Egy adott eset determinisztikus súlyozott automatákból áll, amelyek hasonlóak a szekvenciális automatákhoz.
Kleene-Schützenberger-tétel
A Kleene-Schützenberger tétel kiterjesztése a Kleene tétel súlyozott automaták. A tétel azt állítja, hogy a nem-kommutatív változók formális sorozata egy félgyűrű együtthatóival akkor és csak akkor racionális, ha azt egy súlyozott véges automata felismeri, amelynek a címkék megfelelő súlyai ennek a félgyűrűnek az elemei.
Pólya sorozat
A nem kommutatív változók formális racionális sorai, amelyek egy mezőben együtthatók, figyelemre méltó számtani tulajdonságokkal rendelkeznek, amelyek együtthatóik aritmetikai jellegéhez kapcsolódnak.
A K mezőben együtthatóval rendelkező sorozatot Pólya-sorozatnak nevezzük, ha annak nulla nélküli együtthatói a K * végesen generált alcsoportjában találhatók.
Egy 1921-es Pólya-tétel leírja ezeket a racionális sorozatokat egy változó esetében. Ezt követően Benali Benzaghou 1970-ben és Jean-Paul Bézivin 1987-ben általánosította, ismét egy változóra. Több változó esetét írta le Daniel Smertnig és Jason Bell. arXiv: 1906.07271 A következőképpen szól: A sorozat pontosan akkor Pólya-sorozat, amikor egy egyértelmű súlyozott automata felismeri.
Történelmi megjegyzés
A súlyozott véges automatákat, különösen formális sorozatoknak tekintik, a formális nyelvek általánosításaként Marcel-Paul Schützenberger vezette be az 1960-as évek elején. A traktátusban a szokásos automaták általánosításának formájában szisztematikus kiállítást mutatott be. Samuel Eilenberg . Nevezetesen bevezette a „ - -automaton” kifejezést, hogy kijelöljön egy automatát az ábécén és a félgyűrű értékeit . Újabban Jacques Sakarovitch könyve, valamint Droste, Kuich és Vogler kézikönyve kibővítette a területet, és gyakorlati alkalmazásokat is tartalmazott.
K{\ displaystyle K}Σ{\ displaystyle \ Sigma}Σ{\ displaystyle \ Sigma}K{\ displaystyle K}
Kétéves konferencia
Kétévente tudományos konferenciát rendeznek a Súlyozott automaták: elmélet és alkalmazások (rövidítve WATA ) címmel, amelyet a súlyozott automatáknak szentelnek. 2020-ban a konferenciára Marseille-ben kerül sor.
Megjegyzések és hivatkozások
-
Sakarovich 2003 különbséget tesz az általa címkének nevezett termék vagy az eredmény és az érték között, amelyet számításnak hív . Droste, Kuich és Vogler 2009 csak a termék súlyát nevezi .μ(q0,nál nél1,q1)⋯μ(qnem-1,nál nélnem,qnem){\ displaystyle \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n})}λ(q0)μ(q0,nál nél1,q1)⋯μ(qnem-1,nál nélnem,qnem)θ(qnem){\ displaystyle \ lambda (q_ {0}) \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n} ) \ theta (q_ {n})}μ(q0,nál nél1,q1)⋯μ(qnem-1,nál nélnem,qnem){\ displaystyle \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n})}
-
Ez Sakarovich 2009. évi automatája , 2.15. Gyakorlat, 437. oldal.
-
Kostolányi Peter , „ A determinisztikus súlyozott automatákról ”, Information Processing Letters , vol. 140,2018, P. 42–47 ( DOI 10.1016 / j.ipl.2018.08.005 ).
-
A kiterjesztések és változatai, lásd például Droste, Kuich és Vogler 2009 .
-
George Pólya , „ Arithmetische Eigenschaften der Reihenentwicklungen racionális Funktionen. », J. Reine Angew. Math. , vol. 151,1921, P. 1–31.
-
Bénali Benzaghou, „ Hadamardi algebrai ”, bika. Soc. Math. Franciaország , vol. 98,1970, P. 209–252 ( online olvasás , hozzáférés : 2019. december 10. ).
-
Jean-Paul Bézivin, „ Lineáris visszatérő szekvenciák nem nulla karakterisztikában ”, Bull. Soc. Math. Franciaország , vol. 115, n o 21987, P. 227-239 ( online olvasás , hozzáférés : 2019. december 10. ).
-
Jason Bell és Daniel Smertnig, „ Nem kommutatív racionális Pólya-sorozat ”, Arxiv ,2019( arXiv 1906.07271 ).
-
Schützenberger 1961 .
-
Eilenberg 1974 .
-
Sakarovich 2003 .
-
Droste, Kuich és Vogler 2009 .
-
WATA 2020 konferencia weboldala .
Bibliográfia
- Olivier Carton , hivatalos nyelvek, kiszámíthatóság és összetettség ,2008[ a kiadás részlete ] ( online olvasható )
-
Marcel-Paul Schützenberger, „ Az automaták családjának meghatározásáról ”, Information and Control , vol. 4,1961, P. 245–270 ( online olvasás ).
- Manfred Droste, Werner Kuich és Heiko Vogler (szerkesztők), Súlyozott automaták kézikönyve , Springer-Verlag, koll. "Monográfiák az elméleti informatikában",2009, xvii + 608 o. ( ISBN 978-3-642-01491-8 , DOI 10.1007 / 978-3-642-01492-5 , zbMATH 1200.68001 , SUDOC 139029907 )
- Samuel Eilenberg, Automaták, Nyelvek és gépek, Vol. A , Academic Press,1974( ISBN 978-0-12-234001-7 )
-
Jacques Sakarovitch, Az automaták elméletének elemei , Vuibert,2003, 816 p. ( ISBN 978-2-7117-4807-5 )- angol fordítás javításokkal: (en) Jacques Sakarovitch, Elements of Automata Theory , Cambridge, Cambridge University Press,2009, 758 p. ( ISBN 978-0-521-84425-3 )
- (en) John E. Hopcroft , Rajeev Motwani és Jeffrey D. Ullman , Bevezetés az automata elméletbe, a nyelvek és a számítás , Addison-Wesley ,2007, 3 e . ( ISBN 978-0-32146225-1 )
- Laure Daviaud, „Súlyozott automaták elzárása és ekvivalenciája: valószínűségi és Max-Plus esetek” , a nyelv és az automatika elmélete és alkalmazásai között. LATA 2020 , Springer, Cham, koll. " Előadási jegyzetek a számítástechnikában" ( n: o 12038),2020( ISSN 0302-9743 , DOI 10.1007 / 978-3-030-40608-0_2 ) , p. 17–32
Kapcsolódó cikkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">