Algorithmic Model Theory

Model Constructions and Decompositions

An invaluable tool in Algorithmic Model Theory are operations that are compatible with a given logic in the sense that, when applying the operation, one can compute the theory of the result from the theories of the arguments. Classical examples of such operations are interpretations, the products of Feferman and Vaught (for first-order logic) and the generalised sums of Shelah (for monadic second-order logic). Such operations have many applications. The survey [BCL07] gives an overview with emphasis on operations that are compatible with first-order logic or with monadic second-order logic. Such operations have many applications.

  1. They yield a notion of reduction between classes of structures. For instance, every structure in which some structure with undecidable theory may be interpreted has an undecidable theory – a classical approach sincethe work of Tarski and Mostowski.
  2. In algorithmic model theory one can use operations that are compatible with logical theories to represent (infinite) structures by finite terms.Such term representations provide a uniform formalism to describe classes of finitely presentable structures. It encompasses nearly all classes considered in the literature yielding a unification of their definitions, which originally where based on ad-hoc methods like automata, term rewriting systems,grammars, etc.
  3. Besides algorithmic applications of term representations one can also use terms to obtain decompositions of representable structures. Dependingon the choice of operations, it is possible to develop a structure theory for the given class [B06].

Bibliography

[BCL07] Achim Blumensath, Thomas Colcombet, and Christof Löding, Logical theories and compatible operations, in Logic and automata: History and Perspectives, (J. Flum, E. Grädel, T. Wilke, eds.), Amsterdam University Press, 2007, pp. 72-106.

[B06] Achim Blumensath, A Model Theoretic Characterisation of Clique-Width, Annals of Pure and Applied Logic, 142(2006), pp. 321-350.

A A A | Print Print | Impressum Legal note | Contact Contact
    zum Seitenanfangzum Seitenanfang