Reduced Reversible Automata

Még mindig DCFS. Giovanna J. Lavado, Giovanni Pighizzini és Luca Prigioniero írtak egy cikket ide Minimal and Reduced Reversible Automata címmel, mesélek erről is.

Még mindig folytatva az automata vonalat, ezúttal $(Q,\Sigma,\delta,q_0,F)$ lesz, ami a fejünkben van (tehát egy kezdő- és akármennyi végállapot, determinisztikus), nyelvet akarunk vele felismerni. Ezúttal az automatánk parciális is lehet, vagyis nem feltétlen van minden $q$ állapotból minden $a$ betűre kifelé átmenet.

Egyesek szerint a "reverzibilis" rendszerek jók, mert.. és itt szoktak mondani valamit arról, hogy az irreverzibilis rendszerekben amikor információt veszítünk, akkor hő generálódik (itt szoktam úgy nézni, hogy wtf?), és ezért a reverzibilis rendszerek jók, mert nem melegszenek annyira. Hát egészség, biztos így van. Biztos.

Mindenesetre, egy (parciális!) automatát reverzibilisnek hívunk, ha minden $q$ állapotra és $a$ betűre legfeljebb egy olyan $p$ állapot van, amire $p\cdot a=q$. Ez pl. nem az:

mert a $q$-ba két helyről is lehet $b$-vel jönni. Egyébként ez az $(aa)^*+a^*ba^*$ nyelvnek a minimális ( == legkisebb állapotszámú) automatája. Arról ugye tudjuk, hogy izomorfizmus erejéig egyértelmű.

Viszont van vele ekvivalens reverzibilis automata, például ez a kettő:

és hát ezek már mutatják az első problémát, mert három vagy kevesebb állapotból nem lehet ezzel ekvivalens reverzibilis automatát csinálni, ezek pedig nem izomorfak. Tehát az első, amit észreveszünk, hogy a minimális állapotszámú reverzibilis automata az nem egyértelmű. Már ha van, mert persze nem minden nyelvhez van egyáltalán reverzibilis automata. Ha a minimális automatában van olyan $p\neq q$ és $a$ betű meg $w$ szó, hogy $p\cdot a=q\cdot a$ és $q\cdot aw=q$, akkor nem lehet reverzibilissé tenni az automatát, ha nincs benne ilyen, akkor pedig azzá lehet, az ilyennek látszó karakterizációkat hívják "forbidden pattern characterization"-nak, és pl. azt is mutatja, hogy annak eldöntése, hogy egy input automatával van-e ekvivalens reverzibilis, az NL-beli, mert csak végig kell forciklusolnunk a $p$-ket, $q$-kat és $a$-kat és mindegyikre ellenőrizni a $p\cdot a=q\cdot a$ egyenlőséget, aztán ha egyenlő, akkor nézni $q\cdot a$-ból $q$-ba egy elérhetőséget.

A másik fogalom, amit tanítani szoktunk fonyából, az a redukált automata, ez igényel némi előkészületet. Két állapot, $p$ és $q$ ekvivalens, ha belőlük kiindulva ugyanazokat a szavakat fogadja el az automata (azaz, ha minden $w$-re $p\cdot w\in F$ pontosan akkor, ha $q\cdot w\in F$). Most pl. a $q_1$ és a $q_2$ mindkét reverzibilis automatában ekvivalens, mert belőlük indulva az $a^*$ nyelvet fogadja el az automata (és ha kap $b$-t, ledöglik). Mivel $\varepsilon$ is játszik, ezért pl. két ekvivalens állapot vagy egyszerre végállapot, vagy nem.

Automata-minimalizálásra egy valid (és a klasszikus esetben teljesen jó) algoritmus az, hogy ekvivalens állapotokat próbálunk összevonogatni: ha $p$-t és $q$-t akarjuk mergelni, akkor őket összevonásra megjelöljük, és eztán összevonjuk azokat is, amiket "emiatt muszáj", azaz minden $a$ betűre a $p\cdot a$ és $q\cdot a$ állapotot is összevonásra meg kell jelöljük. Így kialakulnak összevonandó halmazok; ha a végeredményben összevonandó halmazok valamelyikében van végállapot is és nem végállapot is, akkor $p$-t és $q$-t nem lehet összevonni (mert nem voltak ekvivalensek), egyébként meg összevonjuk a megfelelő halmazokat, kapunk egy kisebb automatát és ezt addig folytatjuk, amíg már nincs összevonható állapot. A kapott automata klasszikus esetben mindig minimális lesz. Parciális automatákra annyival van kibővítve, hogy először eldobálunk minden állapotot, ami nem érhető el a kezdőállapotot, aztán ha van csapdaállapot, ahonnan az automata nem fogad el semmilyen szót, azaz ahonnan nem érhető el végállapot, azt is eldobáljuk - ettől parciális automata lehet egy eredetileg nem parciális is - és ha összevonogatás közben $p$-t és $q$-t úgy akarjuk összevonni, hogy $p\cdot a$ és $q\cdot a$ közül az egyik definiált, a másik meg nem, akkor őket szintén nem lehet össevonni.

Egy automatát redukáltnak hívunk, ha nincsenek összevonható állapotai. Parciális automatákra igaz, hogy a redukált automaták pont a minimálisak.

Egy reverzibilis automatát hívjunk redukált reverzibilis automatának, ha nem tudunk úgy állapotokat összevonni benne, hogy az eredmény még mindig redukált automata legyen. A fenti két négyállapotú automata pl. mindkettő redukált reverzibilis, hiszen eleve csak a $q_1$ és a $q_2$ az ekvivalens állapot, tehát max őket tudnánk összevonni, de ha megpróbáljuk, akkor pont megkapjuk az eredeti, háromállapotú automatánkat, ami viszont nem reverzibilis. Tehát egyikben se tudunk összevonni senkit, ezért ők redukáltak.

De redukált ám ez is:

Ez is ekvivalens a többivel (annyi történik ugye, hogy az az eredetileg egy darab állapotot, ami elfogadja az $a^*$ végét a szónak, azt szétszedjük valahány körbekötött állapotba). Viszont ha pl. össze akarjuk vonni bármelyik két ekvivalens állapotát, nem lesz reverzibilis az eredmény. Ha ezt valaki nem hiszi el (nagyon helyes), akkor pl. megpróbálhatja mondjuk összevonni a $q_1$-et és a $q_3$-at. Akkor $q_1\cdot a=q_2$ és $q_3\cdot a=q_4$ miatt $q_2$-t és $q_4$-et is össze kell vonni egymással. Akkor $q_2\cdot a=q_3$ és $q_4\cdot a=q_5$ miatt $q_3$-at és $q_5$-öt is össze kell vonni; mivel $q_3$-at $q_1$-gyel is össze akarjuk vonni, ezért eddig ott tartunk, hogy össze kéne vonni a $\{q_1,q_3,q_5\}$ halmazt is és a $\{q_2,q_4\}$ halmazt is. Csakhogy $q_3\cdot a=q_4$ és $q_5\cdot a=q_1$ miatt össze kéne vonni a $q_4$-et és a $q_1$-et is egymással, tehát mind az öt állapotot össze kell vonni egymással (és ugyanezt kapjuk egyébként, ha az alsó öt közül bármelyik kettőt megpróbáljuk összevonni). Ha viszont összevonjuk őket, akkor visszakapjuk az eredeti, háromállapotos automatát, ami nem reverzibilis. Ezért ennek a hétállapotú automatának nem tudjuk állapotait összevonni úgy, hogy reverzibilis automatát kapjunk, ezért ez egy redukált reverzibilis automata.

Ami azt jelenti, hogy a redukált és a minimális szavak reverzibilis automatákra nem jelentik ugyanazt. Sőt: az $5$ helyett akármilyen $P$ prímszámot is írhatunk az előző példába, ha egy $P$ méretű körnek két állapotát megpróbáljuk összevonni, akkor azt fogjuk kapni, hogy mindet össze kéne vonni, ami meg nem lesz reverzibilis. Prímszámból pedig végtelen sok van. Ami pedig azt jelenti, hogy

vannak olyan nyelvek, amikhez végtelen sok redukált reverzibilis automata tartozik

és a kérdés az, hogy

mikor igaz egy minimális automatára, hogy végtelen sok vele ekvivalens redukált reverzibilis automata van?

Erről a következőt tudják a szerzők eddig. Ha kiindulunk egy minimális (nem reverzibilis) automatából, abból úgy tudunk reverzibilist építeni, hogy némelyik állapotát megduplázzuk/megtriplázzuk/stb, amennyi épp kell (ez azt jelenti, hogy a készített reverzibilis automatában két-három-stb olyan állapot lesz, ami az eredeti állapottal ekvivalens), másokat meg nem feltétlenül kell. Ha egy állapotot nem feltétlenül kell duplikálnunk (azaz ha van olyan ekvivalens reverzibilis automata, amiben ugyanúgy csak egy olyan állapot van, ami ezzel ekvivalens), akkor ez az állapot az automata reverzibilis részében van, ha pedig muszáj duplikálnunk, akkor az az irreverzibilis részében van. Pl. az eredeti automatánk $q_i$ és $p$ állapotai a reverzibilis részben vannak (mert pl. a négyállapotú automatákban ezekből még mindig csak $1-1$ példány van), viszont a $q$ állapot az az irreverzibilisben (a bele menő két nyíl miatt muszáj megdupláznunk). Ezekről a részekről azt érdemes tudni, hogy a reverzibilis részből vezethet átmenet az irreverzibilis részbe, de vissza nem (ahogy a példában se lehet már visszajönni $q$-ból a másik kettőbe).

Szóval a következőt tudják a szerzők eddig:

1. Ha az irreverzibilis részben van kör, akkor végtelen sok ekvivalens redukált reverzibilis automata van.
2. Ez a feltétel csak elegendő, de nem szükséges.

Megkérdeztem Giovannát és azt mondta, hogy pl. ennek az irreverzibilis részében (az alsó két állapot) nincs kör, de mégis végtelen sok ekvivalens redukált reverzibilis automata van hozzá:

hát mit mondhatnék, biztos így van. Azt látom, hogy $q_5$ és $q_6$ vannak az irreverzibilis részben, azt is látom, hogy ez az automata minimális, tehát $q_5$-öt és $q_6$-ot kell duplikálni, azt is látom, hogy $2-2$ példány elég belőlük ($q_1$ alá kötve mondjuk), de azt egyelőre még nem látom, hogy ebből hogy lesz akármekkora nagy redukált irreverzibilis. Ja meg azt is látom persze, hogy nincs kör az irreverzibilis részében.

Tehát a kérdés még egyszer: karakterizálni kéne azokat a minimális automatákat, amikkel végtelen sok ekvivalens redukált reverzibilis automata van.

Egyébként azt is tudják, hogy pontosan akkor van izomorfizmus erejéig egyértelmű minimális reverzibilis automata, ha a minimális automata irreverzibilis részében minden állapotba pontosan egyféle betű visz. Pl. a háromállapotos automatánkban az elején a $q$ nem ilyen volt, mert belevitt $a$ is és $b$ is. Ezért nem volt egyértelmű a minimális reverzibilis, hanem kettőt is találtunk.

Completely Reachable Automata

na szóval DCFSen vagyok.

Az egyik meghívott előadó a Mikhail Volkov, aki beszélt erről a work-in-progress papírjukról, ami nekem tetszik. Megpróbálom összefoglalni a nekem érdekes kérdést.

Az alapfelállás, hogy van egy determinisztikus automatánk, mondjuk $(Q,\Sigma,\delta)$ (most nem akarunk vele nyelvet felismerni, ezért nem rakok bele kezdő- meg végállapotot). Ahogy szoktuk, a $\delta$ átmenetfüggvényt nem írjuk ki, hanem $\delta(q,a)$ helyett csak $q\cdot a$-t írok; ha $w$ egy szó, akkor $q\cdot w$ jelöli azt az állapotot, ahova a $w$ szó elviszi a $q$ állapotot; és ha $P\subseteq Q$ egy állapothalmaz, akkor $P\cdot w$ jelöli a $\{p\cdot w:p\in P\}$ halmazt, ahova a $P$-beli állapotokat elviszi a $w$ szó.

Egy $P\subseteq Q$ állapothalmaz elérhető, ha van olyan $w$ szó, amire $Q\cdot w=P$. Nyilván mivel minden állapot kerül valahova $w$ hatására, csak nemüres állapothalmazok elérhetőek, és $Q\cdot\varepsilon=Q$ (megint $\varepsilon$ az üres szó, bocs $\lambda$-fanok), tehát $Q$ elérhető, $\emptyset$ pedig nem.

Egy automatát pedig "completely reachable", legyen mondjuk CR-automatának nevezünk, ha minden nemüres állapothalmaza elérhető. Például, ez:

ami amúgy a négyállapotú Cerny-automata, erről is majd talán írok pár szót, ez pl. CR-automata. Aki ellenőrizni szeretné, lerajzoltam a hatványhalmaz-automatájának egy részletét, amiből látszik, hogy minden nemüres állapothalmaza elérhető, pl. az $\{1,3\}$ halmazba a $baaba$ szó viszi el $Q$-t:

Kérdés: eldönthető-e polinomidőben, hogy egy input automata CR-automata-e?

Amit ezzel kapcsolatban tudni lehet:

1. ha az input egy $(Q,\Sigma,\delta)$ automata és egy $P\subseteq Q$ állapothalmaz, akkor PSPACE-teljes azt eldönteni, hogy $P$ elérhető-e.
2. ha a fenti $P$ egyelemű, akkor P-ben van.
3. ha a fenti $P$ kételemű, akkor már kételemű ábécére is coNP-nehéz.
4. ha végigiterálunk az állapothalmazokon és mindegyiket megpróbáljuk elérni nemdeterminisztikusan, újrafelhasználva a tárat, akkor ugye PSPACE=NPSPACE (thx Savitch-tétel) miatt látszik, hogy a kérdés PSPACE-beli.

Namost attól, hogy egy-egy input $P\subseteq Q$-ra az elérhetőség PSPACE-teljes, attól még lehet, hogy az a kérdés, hogy mindegyik elérhető-e, P-ben van. (pl. gráfokra ha az input egy $n$-csúcsú $G$ gráf és egy $1\leq k\leq n$ szám, és azt kérdezzük, van-e $G$ darab páronként szomszédos csúcs, az úgy NP-teljes, de ha azt kérdezzük, hogy minden ilyen $k$-ra van-e, az P-ben van, mert csak a teljes $n$-csúcsú gráfokra igaz.)

Van még több másik, érdekesnek tűnő kérdés is a papírban, akit érdekel a téma, nézzen rá :)