Existential and positive theories of equations in graph products

Diekert, Volker; Lohrey, Markus

Existential and positive theories of equations in graph products

dc.contributor.author	Diekert, Volker	de
dc.contributor.author	Lohrey, Markus	de
dc.date.accessioned	2002-01-29	de
dc.date.accessioned	2016-03-31T07:58:17Z
dc.date.available	2002-01-29	de
dc.date.available	2016-03-31T07:58:17Z
dc.date.issued	2001	de
dc.date.updated	2013-07-02	de
dc.description.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.	de
dc.identifier.other	097161969	de
dc.identifier.uri	http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-9916	de
dc.identifier.uri	http://elib.uni-stuttgart.de/handle/11682/2497
dc.identifier.uri	http://dx.doi.org/10.18419/opus-2480
dc.language.iso	en	de
dc.relation.ispartofseries	Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2001,10	de
dc.rights	info:eu-repo/semantics/openAccess	de
dc.subject.classification	Grammatik , Formale Sprache	de
dc.subject.ddc	004	de
dc.title	Existential and positive theories of equations in graph products	en
dc.type	workingPaper	de
ubs.fakultaet	Fakultät Informatik, Elektrotechnik und Informationstechnik	de
ubs.institut	Institut für Formale Methoden der Informatik	de
ubs.opusid	991	de
ubs.publikation.typ	Arbeitspapier	de
ubs.schriftenreihe.name	Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik	de

Files

Original bundle

Now showing 1 - 1 of 1

Name:: TR-2001-10.pdf
Size:: 322.22 KB
Format:: Adobe Portable Document Format

Download

Collections

05 Fakultät Informatik, Elektrotechnik und Informationstechnik