Problem der Äquivalenz zweier Regulärer Ausdrücke mit Potenzierung

Einfache Sprache

Def. Problem der Äquivalenz zweier Regulärer Ausdrücke mit Potenzierung

Die Sprache $\mathrm{EQ_{REXP}}$ enthält Paare Regulärer Ausdruck mit Potenzierung, die die gleiche Sprache erkennen. Also

$$\mathrm{EQ_{REXP}} = \text{EQ-REXP} = \{\langle R,S\rangle\mid R \text{ und } S \text{ sind äquivalente Reguläre Ausdrücke mit Potenzierung}\}$$

Es ist eine Generalisierung des EQ-REG Problems.

Sätze

• SATZ EQ-REXP ist EXPSPACE-vollständig