A Crevice on the Crane Beach: Finite-Degree Predicates

2017/01/01 by Michaël Cadilhac, Cadilhac, Michaël, Charles Paperman +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Algebra and Logic #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1701.02673

openalex publication_date 2017/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

First-order logic (FO) over words is shown to be equiexpressive with FO equipped with a restricted set of numerical predicates, namely the order, a binary predicate MSB₀, and the finite-degree predicates: FO[Arb] = FO[

Related

• Finite-Degree Predicates and Two-Variable First-Order Logic
• Positive first-order logic on words
• Fragments of first-order logic over infinite words
• One Quantifier Alternation in First-Order Logic with Modular Predicates
• Languages of Dot-depth One over Infinite Words