On the expressiveness of Büchi arithmetic

DOI10.1007/978-3-030-71995-1_16OpenAlexW3109452257MaRDI QIDQ2233416

Jakub Różycki, Christoph Haase

Publication date: 18 October 2021

Full work available at URL: https://arxiv.org/abs/2010.12892

zbMATH Keywords

quantifier eliminationregular languageslogical theoriesautomatic structureslogical definability

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

On the existential arithmetics with addition and bitwise minimum

Cites Work

• Unnamed Item
• Unnamed Item
• The unreasonable ubiquitousness of quasi-polynomials
• Unary finite automata vs. arithmetic progressions
• Finite automata and unary languages
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Logic and \(p\)-recognizable sets of integers
• Weak Second‐Order Arithmetic and Finite Automata
• Definable relations and first-order query languages over strings
• The taming of the semi-linear set
• Characterizing regular languages with polynomial densities
• Bounded Algol-Like Languages

This page was built for publication: On the expressiveness of Büchi arithmetic