Diophantine equations, Presburger arithmetic and finite automata

DOI10.1007/3-540-61064-2_27MaRDI QIDQ5878899zbMATH OpenOpenAlexFDO

Authors Alexandre Boudet, Hubert Comon

Publication date 23 February 2023

Published in Trees in Algebra and Programming — CAAP '96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61064-2_27

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) First-order arithmetic and fragments (03F30) Linear Diophantine equations (11D04) Decidability (number-theoretic aspects) (11U05)

Recommendations

• Components of \(V(\rho)\otimes V(\rho)\)
• A note on branching of \(V( \rho )\)
• scientific article; zbMATH DE number 66791
• An algebraic proof of the PRV conjecture for very regular weights.
• scientific article; zbMATH DE number 3865525

Cites work

• An efficient incremental algorithm for solving systems of linear diophantine equations
• scientific article; zbMATH DE number 3930337 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• The computational complexity of logical theories

Cited in

(23)

• The convex hull of a regular set of integer vectors is polyhedral and effectively computable
• Automatic verification of recursive procedures with one integer parameter.
• Counting the solutions of Presburger equations without enumerating them.
• On iterating linear transformations over recognizable sets of integers
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• A note on branching of \(V( \rho )\)
• Structural Presburger digit vector automata
• Components of \(V(\rho)\otimes V(\rho)\)
• A class of polynomially solvable range constraints for interval analysis without widenings
• Tree languages and branched groups
• More than 1700 years of word equations
• ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS
• On the use of non-deterministic automata for Presburger arithmetic
• scientific article; zbMATH DE number 2038746 (Why is no real title available?)
• scientific article; zbMATH DE number 7089069 (Why is no real title available?)
• Bounds on the automata size for Presburger arithmetic
• Compiler Construction
• Behavior decompositions and two-sided diophantine equations
• Proving safety properties of infinite state systems by compilation into Presburger arithmetic
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• Reasoning About Regular Properties: A Comparative Study
• Formalizing the Logic-Automaton Connection
• On the solvability of a class of Diophantine equations and applications

This page was built for publication: Diophantine equations, Presburger arithmetic and finite automata

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