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á :)