Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2548
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Lohrey, Markus | de |
dc.contributor.author | Ondrusch, Nicole | de |
dc.date.accessioned | 2005-04-13 | de |
dc.date.accessioned | 2016-03-31T07:58:30Z | - |
dc.date.available | 2005-04-13 | de |
dc.date.available | 2016-03-31T07:58:30Z | - |
dc.date.issued | 2005 | de |
dc.identifier.other | 117300802 | de |
dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-22557 | de |
dc.identifier.uri | http://elib.uni-stuttgart.de/handle/11682/2565 | - |
dc.identifier.uri | http://dx.doi.org/10.18419/opus-2548 | - |
dc.description.abstract | This paper investigates the word problem for inverse monoids generated by a set A subject to relations of the form e=f, where e and f are both idempotents in the free inverse monoid generated by A. It is shown that for every fixed monoid of this form the word problem can be solved in polynomial time which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node x to a node y that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. Finally, it is shown that the Cayley-graph of the free inverse monoid has an undecidable monadic second-order theory. | en |
dc.language.iso | en | de |
dc.relation.ispartofseries | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2005,2 | de |
dc.rights | info:eu-repo/semantics/openAccess | de |
dc.subject.classification | Cayley-Graph , Monoid , Komplexität | de |
dc.subject.ddc | 004 | de |
dc.subject.other | inverse monoids , word problem , generalized word problem , Cayley-graphs , complexity , decidability | en |
dc.title | Inverse monoids : decidability and complexity of algebraic questions | en |
dc.type | workingPaper | de |
dc.date.updated | 2013-07-08 | de |
ubs.fakultaet | Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
ubs.institut | Institut für Formale Methoden der Informatik | de |
ubs.opusid | 2255 | 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_2005_02.pdf | 225,9 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.