Bibliograph. Daten | Lohrey, Markus; ,: Complexity Results for Confluence Problems. Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1999/05. 22 Seiten, englisch.
|
CR-Klassif. | F.4.2 (Grammars and Other Rewriting Systems) F.4.3 (Formal Languages)
|
Kurzfassung | We study the complexity of the confluence problem for restricted kinds of semi--Thue systems, vector replacement systems and general trace rewriting systems. We prove that confluence for length--reducing semi--Thue systems is P--complete and that this complexity reduces to $\AC^1$ in the monadic case (where all right--hand sides consist of at most one symbol). For length--reducing vector replacement systems we prove that the confluence problem is PSPACE--complete and that the complexity reduces to NP and P, respectively, for monadic vector replacement systems and special vector replacement systems (where all right--hand sides are empty), respectively. Finally we prove that for special trace rewriting systems, confluence can be decided in polynomial time and that the extended word problem for special trace rewriting systems is undecidable
|
Volltext und andere Links | HTML (aus PostScript generiert)
|
Abteilung(en) | Universität Stuttgart, Institut für Informatik, Theoretische Informatik
|
Eingabedatum | 4. März 1999 |
---|