Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T15:12:04.981Z Has data issue: false hasContentIssue false

First-order and counting theories of ω-automatic structures

Published online by Cambridge University Press:  12 March 2014

Dietrich Kuske
Affiliation:
Universität Leipzig, Institut Für Informatik, Postfach 100920, D-04009 Leipzig, Germany, E-mail: kuske@informatik.uni-leipzig.de
Markus Lohrey
Affiliation:
Universität Leipzig, Institut Für Informatik, Postfach 100920, D-04009 Leipzig, Germany, E-mail: lohrey@informatik.uni-leipzig.de

Abstract

The logic extends first-order logic by a generalized form of counting quantifiers (“the number of elements satisfying … belongs to the set C”). This logic is investigated for structures with an injectively ω-automatic presentation. If first-order logic is extended by an infinity-quantifier, the resulting theory of any such structure is known to be decidable [6]. It is shown that, as in the case of automatic structures [21], also modulo-counting quantifiers as well as infinite cardinality quantifiers (“there are many elements satisfying …”) lead to decidable theories. For a structure of bounded degree with injective ω-automatic presentation, the fragment of that contains only effective quantifiers is shown to be decidable and an elementary algorithm for this decision is presented. Both assumptions (ω-automaticity and bounded degree) are necessary for this result to hold.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable