On the expressiveness of Büchi arithmetic

DOI10.1007/978-3-030-71995-1_16MaRDI QIDQ2233416zbMATH OpenOpenAlexFDO

Authors Christoph Haase, Jakub Różycki

Publication date 18 October 2021

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

automatic structureslogical definabilitylogical theoriesquantifier eliminationregular languages

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(8)

• scientific article; zbMATH DE number 7440178 (Why is no real title available?)
• On the existential arithmetics with addition and bitwise minimum
• On the Expressiveness of B\"uchi Arithmetic
• Universal quantification makes automatic structures hard to decide
• Formal languages and arithmetic theories: recent results and open problems
• Integer linear-exponential programming in NP by quantifier elimination
• Existential definability of unary predicates in Büchi arithmetic
• Word equations with length constraints via weak arithmetics and matrix reachability problems

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

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