Structures of bounded partition width [Elektronische Ressource] / vorgelegt von Achim Blumensath

S  BP W   ,   -           Diplom-InformatikerAchimBlumensath UniversitätsprofessorDr.ErichGrädelUniversitätsprofessorDr.JörgFlum   .November  DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfügbar.mPreface vP   monadic second-order logic startedTaroundwiththeworkofBüchi,Elgot,McNaughton,andRa-binonthemonadictheoriesofthenaturalnumbersandtheinfinitebinarytree.?isresearchrevealedacloseconnectionbetwe en MSOandautomatatheoryleadingtoautomata-baseddecisionproceduresfor a wide range of monadic theories. A wealth of applications ofthese results ensued in the fields of modal logic and automatic veri-fication.Notonly didmanydecidability resultsdirectlyfollowfromthe decidability of the MSO-theory of the binary tree, but also theautomata-theoretictechniquesemployedby Büchi and Rabin couldbeadoptedtoobtainefficientdecisionproceduresforweakerlogics.Asfarasfurtherdevelopmentonmonadicsecond-orderlogicitselfisconcerned,Shelahgavenewproofsoftheirresultsbypurelymodeltheoretic means and, together with Gurevich, they investigated themonadictheoryoflinearorders.