Contributions to a trace theory beyond Mazurkiewicz traces [Elektronische Ressource] / Dietrich Kuske

Contributions to a Trace Theory beyondMazurkiewicz TracesHABILITATIONSSCHRIFTzur Erlangung des akademischen GradesDoctor rerum naturalium habilitatus(Dr. rer. nat. habil.)vorgelegtder Fakult¨at Mathematik und Naturwissenschaftender Technischen Universitat¨ DresdenvonDr. rer. nat. Dietrich Kuskegeboren am 8. Juni 1965 in Ku¨hlungsbornGutachter: Prof. Dr. Volker DiekertProf. Dr. Manfred DrosteProf. Dr. Wolfgang ThomasEingereicht am: 20. Dezember 1999Tag der Verteidigung: 21. Dezember 2000URN: urn:nbn:de:gbv:ilm1-2011200051iiContentsIntroduction v1 Basic definitions 11.1 Order theoretic definitions . . . . . . . . . . . . . . . . . . . . . . 11.2 Monoid theoretic definitions . . . . . . . . . . . . . . . . . . . . . 41.3 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Some notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8I Asynchronous cellular machines 92 Σ-dags and ACMs 113 Decidability results 213.1 Notational conventions and definitions . . . . . . . . . . . . . . . 213.2 Well-structured transition systems . . . . . . . . . . . . . . . . . . 223.3 The emptiness is decidable for ACMs . . . . . . . . . . . . . . . . 354 The undecidability results 455 The expressive power of ACAs 615.1 From ACAs to MSO . . . . . . . . . . . . . . . . . . . . . . . . . 625.2 (Σ;k)-dags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .