Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2480
Authors: Diekert, Volker
Lohrey, Markus
Title: Existential and positive theories of equations in graph products
Issue Date: 2001
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2001,10
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-9916
http://elib.uni-stuttgart.de/handle/11682/2497
http://dx.doi.org/10.18419/opus-2480
Abstract: We prove that the existential theory of equations with normalized rational constraints in a fixed graph product of finite monoids, free monoids, and free groups is PSPACE-complete. Under certain restrictions this result also holds if the graph product is part of the input. As the second main result we prove that the positive theory of equations with recognizable constraints in graph products of finite and free groups is decidable.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR-2001-10.pdf322,22 kBAdobe PDFView/Open


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