Expressive power of unary counters

DOI10.1007/3-540-63246-8_3MaRDI QIDQ4362726zbMATH OpenFDO

Authors Michael Benedikt, H. Jerome Keisler

Publication date 13 November 1997

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63246-8_3

zbMATH Keywords

counting operatorexpressive powerfinite structuresnonstandard models of arithmetic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Nonstandard models of arithmetic (03H15)

Review text

Limits on the expressive power for finite structures of the language \(L(\text{Ct})\) are shown by proving that it is not possible to count the number of classes of an equivalence relation in this language. Here, \(L(\text{Ct})\) is formed by adding to first-order logic an operator \(\text{count}\{x\mid\varphi(x)\}\), which builds a term of sort \(\mathbb{N}\) that counts the number of elements satisfying \(\varphi\). Arbitrary integer predicates and functions are applicable to these terms. The authors prove the above non-expressibility result using nonstandard models of arithmetic. For the entire collection see [Zbl 0868.00014].

Recommendations

• On the expressive power of counting
• The expressive power of fixed-point logic with counting
• Logics with counting and local properties
• Unary quantifiers, transitive closure, and relations of large degree

Cited in

(4)

• Lower bounds for invariant queries in logics with counting.
• Arithmetic, first-order logic, and counting quantifiers
• On the expressive power of counting
• Advances in algorithmic meta theorems (invited paper)

This page was built for publication: Expressive power of unary counters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4362726)