Entscheidbare Fälle des Postschen Korrespondenzproblems
Abstract:
Das Postsche Korrespondenzproblem fragt nach nichttrivialen Elementen in der Gleichheitsmenge zweier Morphismen. Es handelt sich um ein unentscheidbares Problem. Wir stellen umfassend und einheitlich dar, welche Möglichkeiten es gibt, Instanzen des Postschen Korrespondenzproblems zu klassifizieren. Wir charakterisieren die Koinzidenzmenge erstmals als rationale Relation. Wir lösen konkrete Instanzen schnell und finden so praktische alle bekannten schwierigen kleinen Instanzen.
| Zugehörige Institution(en) am KIT | Fakultät für Informatik – Institut für Algorithmen und Kognitive Systeme (IAKS) |
| Publikationstyp | Hochschulschrift |
| Publikationsjahr | 2008 |
| Sprache | Deutsch |
| Identifikator | urn:nbn:de:swb:90-99795 KITopen-ID: 1000009979 |
| Verlag | Universität Karlsruhe (TH) |
| Art der Arbeit | Dissertation |
| Fakultät | Fakultät für Informatik (INFORMATIK) |
| Institut | Fakultät für Informatik – Institut für Algorithmen und Kognitive Systeme (IAKS) |
| Prüfungsdaten | 12.12.2008 |
| Schlagwörter | Unentscheidbarkeit, Postsches Korrespondenzproblem, Koinzidenzmenge, Hochleistungsrechnen |
| Referent/Betreuer | Vollmar, R. |