2023/05/26 by Daniel Turaev, Turaev, Daniel
Computer Science · #Computability, Logic, AI Algorithms #FOS: Mathematics #Group Theory (math.GR) #Logic (math.LO) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2305.16880
openalex publication_date 2023/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper proves that a plactic monoid of any finite rank will have decidable first order theory. This resolves other open decidability problems about the finite rank plactic monoids, such as the Diophantine problem and identity checking. This is achieved by interpreting a plactic monoid of arbitrary rank in Presburger arithmetic, which is known to have decidable first order theory. We also prove that the interpretation of the plactic monoids into Presburger Arithmetic is in fact a bi-interpretation, hence any two plactic monoids of finite rank are bi-interpretable with one another. The algorithm generating the interpretations is uniform, which answers positively the decidability of the Diophantine problem for the infinite rank plactic monoid.