Monadic decomposition in integer linear arithmetic

DOI10.1007/978-3-030-51074-9_8MaRDI QIDQ2096441zbMATH OpenOpenAlexFDO

Authors Matthew Hague, Philipp Rümmer, Zhilin Wu, Anthony Widjaja Lin

Publication date 9 November 2022

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

Mathematics Subject Classification ID

Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Cites work

• Decision problems among the main subfamilies of rational relations
• scientific article; zbMATH DE number 1253963 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Monadic decomposability of regular relations
• Monadic decomposition
• On solving word equations using SAT
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• String solving with word equations and transducers: towards a logic for analysing mutation XSS
• Subclasses of Presburger arithmetic and the weak EXP hierarchy
• The power of symbolic automata and transducers
• The taming of the semi-linear set
• Variable independence for first-order definable constraints
• Word equations in nondeterministic linear space

Cited in

(6)

• Quantifier elimination for counting extensions of Presburger arithmetic
• An efficient quantifier elimination procedure for Presburger arithmetic
• Integer linear-exponential programming in NP by quantifier elimination
• An introduction to the theory of linear integer arithmetic (invited paper)
• The complexity of separability for semilinear sets and Parikh automata
• Learning union of integer hypercubes with queries (with applications to monadic decomposition)

Describes a project that uses

Uses Software

• S3

This page was built for publication: Monadic decomposition in integer linear arithmetic

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