2011 | OriginalPaper | Buchkapitel
Logics, Structures and Presentations
verfasst von : Łukasz Kaiser
Erschienen in: Logic and Games on Automatic Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this chapter we review the standard notions of first-order and monadic second-order logic. We introduce linear orders and trees and state a few elementary properties of these structures. We recall the correspondence between monadic second-order logic and automata on infinite words together with basic facts from automata theory . We introduce automatic structures using presentations by automata and characterize them both by first-order and by monadic second-order to first-order interpretations. Finally, we discuss the composition method for monadic second-order logic over linear orders and trees.