On iterating linear transformations over recognizable sets of integers

DOI10.1016/S0304-3975(03)00314-1MaRDI QIDQ1884908zbMATH OpenOpenAlexFDO

Authors B. Boigelot

Publication date 27 October 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00314-1, http://orbi.uliege.be/handle/2268/74862

zbMATH Keywords

AutomataIterationsPresburger arithmeticRecognizable sets of integers

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• On the expressiveness of real and integer arithmetic automata. (Extended abstract)
• Bertrand numeration systems and recognizability
• m-recognizability of sets closed under certain affine functions
• Structural Presburger digit vector automata
• On the recognizability of self-generating sets

Cites work

• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Diophantine equations, Presburger arithmetic and finite automata
• scientific article; zbMATH DE number 3141552 (Why is no real title available?)
• scientific article; zbMATH DE number 47996 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3641577 (Why is no real title available?)
• scientific article; zbMATH DE number 3993564 (Why is no real title available?)
• scientific article; zbMATH DE number 3278338 (Why is no real title available?)
• Logic and p-recognizable sets of integers
• On the base-dependence of sets of numbers recognizable by finite automata
• On the construction of automata from linear arithmetic constraints
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• Presburgerness of predicates regular in two number systems
• Symbolic reachability analysis of FIFO-channel systems with nonregular sets of configurations
• The computational complexity of logical theories
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(13)

• m-recognizability of sets closed under certain affine functions
• Flat Petri nets (invited talk)
• Computable fixpoints in well-structured symbolic model checking
• Model-checking \(\mathrm{CTL}^*\) over flat Presburger counter systems
• A new acceleration-based combination framework for array properties
• Iterating Octagons
• Direct transformations between sets of integers and hilbert polygons
• A calculus for modular loop acceleration
• Termination of linear loops over the integers
• scientific article; zbMATH DE number 6028107 (Why is no real title available?)
• Accelerating Interpolation-Based Model-Checking
• Accelerating loops with arrays
• Algebraic program analysis

Describes a project that uses

Uses Software

• LASH
• MONA

This page was built for publication: On iterating linear transformations over recognizable sets of integers

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