Korsningsproblem utan tomhet

Intersection non-emptiness problem , även känt som finita automaton intersection problem eller non-emptiness of intersection problem , är ett PSPACE-komplett beslutsproblem från automatteorin .

Definitioner

Ett problem med beslut om icke-tomhet definieras enligt följande. Givet en automat som indata, är målet att avgöra om automatens språk är icke-tomt eller inte. Målet är med andra ord att avgöra om det finns en sträng som accepteras av automaten.

Icke-tomhetsproblem har studerats inom automatteorin under många år. Flera vanliga problem utan tomhet har visat sig vara kompletta för komplexitetsklasser som sträcker sig från Deterministic Logspace upp till PSPACE .

Beslutsproblemet för beslut om korsning av icke-tomhet handlar om huruvida skärningspunkten mellan givna språk är icke-tom. Speciellt definieras problemet med icke-tomhet i korsningen enligt följande. Givet en lista över deterministiska finita automater som indata, är målet att avgöra om deras associerade reguljära språk har en icke-tom skärningspunkt eller inte. I andra fall är målet att avgöra om det finns en sträng som accepteras av alla automater i listan.

Algoritm

Det finns en vanlig exponentiell tidsalgoritm som löser intersection non-emptiness-problemet baserat på den kartesiska produktkonstruktionen introducerad av Michael O. Rabin och Dana Scott . Tanken är att alla automaterna tillsammans bildar en produktautomat så att en sträng accepteras av alla automaterna om och bara om den accepteras av produktautomaten. Därför kommer en bredd-först-sökning (eller djup-först-sökning ) i produktautomatens tillståndsdiagram att avgöra om det finns en väg från produktens starttillstånd till ett av produktens sluttillstånd. Huruvida en sådan sökväg existerar eller inte motsvarar att bestämma om någon sträng accepteras av alla automater i listan.

Obs: Produktautomaten behöver inte vara helt konstruerad. Automaterna ger tillsammans tillräcklig information så att övergångar kan bestämmas efter behov.

Hårdhet

Korsningsproblemet med icke-tomhet visade sig vara PSPACE-komplett i ett verk av Dexter Kozen 1977. Sedan dess har många ytterligare hårdhetsresultat visats. Ändå är det fortfarande ett öppet problem att avgöra om det finns några snabbare algoritmer.

* Se en ofullständig lista över relaterade publikationer här .

Relaterad