Existential and positive theories of equations in graph products

Diekert, Volker; Lohrey, Markus

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-2480

Langanzeige der Metadaten

DC Element	Wert	Sprache
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.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.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.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
dc.date.updated	2013-07-02	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
Enthalten in den Sammlungen:	05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:

Datei	Beschreibung	Größe	Format
TR-2001-10.pdf		322,22 kB	Adobe PDF	Öffnen/Anzeigen

Zur Kurzanzeige

Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.

Universität Stuttgart

OPUS - Online Publikationen der Universität Stuttgart