Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2428
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Lohrey, Markus | de |
dc.date.accessioned | 1999-06-15 | de |
dc.date.accessioned | 2016-03-31T07:58:10Z | - |
dc.date.available | 1999-06-15 | de |
dc.date.available | 2016-03-31T07:58:10Z | - |
dc.date.issued | 1999 | de |
dc.identifier.other | 079874053 | de |
dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-4497 | de |
dc.identifier.uri | http://elib.uni-stuttgart.de/handle/11682/2445 | - |
dc.identifier.uri | http://dx.doi.org/10.18419/opus-2428 | - |
dc.description.abstract | 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. | en |
dc.language.iso | en | de |
dc.relation.ispartofseries | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;1999,5 | de |
dc.rights | info:eu-repo/semantics/openAccess | de |
dc.subject.classification | Thue-System , Berechnungskomplexität | de |
dc.subject.ddc | 004 | de |
dc.subject.other | confluence problem , vector replacement systems , semi-Thue systems | en |
dc.title | Complexity results for confluence problems | en |
dc.type | workingPaper | de |
dc.date.updated | 2013-06-27 | de |
ubs.fakultaet | Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
ubs.institut | Institut für Formale Methoden der Informatik | de |
ubs.opusid | 449 | de |
ubs.publikation.typ | Arbeitspapier | de |
ubs.schriftenreihe.name | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
449_1.pdf | 284,33 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.