Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2428
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLohrey, Markusde
dc.date.accessioned1999-06-15de
dc.date.accessioned2016-03-31T07:58:10Z-
dc.date.available1999-06-15de
dc.date.available2016-03-31T07:58:10Z-
dc.date.issued1999de
dc.identifier.other079874053de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-4497de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2445-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2428-
dc.description.abstractWe 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.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;1999,5de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationThue-System , Berechnungskomplexitätde
dc.subject.ddc004de
dc.subject.otherconfluence problem , vector replacement systems , semi-Thue systemsen
dc.titleComplexity results for confluence problemsen
dc.typeworkingPaperde
dc.date.updated2013-06-27de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid449de
ubs.publikation.typArbeitspapierde
ubs.schriftenreihe.nameTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnikde
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
449_1.pdf284,33 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.