Search

In this short survey we describe recent advances on word equations with non-rational constraints in groups and monoids, highlighting the important role that formal languages play in this area., Comment: 12 pages, to appear in the proceedings of DLT 2024. arXiv admin note: text overlap with arXiv:2204.13946

Indexed languages are a classical notion in formal language theory. As the language equivalent of second-order pushdown automata, they have received considerable attention in higher-order model checking. Unfortunately, counting properties are notoriously difficult to decide for indexed languages: So far, all results about non-regular counting properties show undecidability. In this paper, we initiate the study of slice closures of (Parikh images of) indexed languages. A slice is a set of vectors of natural numbers such that membership of $u,u+v,u+w$ implies membership of $u+v+w$. Our main result is that given an indexed language $L$, one can compute a semilinear representation of the smallest slice containing $L$'s Parikh image. We present two applications. First, one can compute the set of all affine relations satisfied by the Parikh image of an indexed language. In particular, this answers affirmatively a question by Kobayashi: Is it decidable whether in a given indexed language, every word has the same number of $a$'s as $b$'s. As a second application, we show decidability of (systems of) word equations with rational constraints and a class of counting constraints: These allow us to look for solutions where a counting function (defined by an automaton) is not zero. For example, one can decide whether a word equation with rational constraints has a solution where the number of occurrences of $a$ differs between variables $X$ and $Y$., Comment: 12 pages, accepted for publication at LICS 2024

In this paper we describe conjugacy geodesic representatives in any dihedral Artin group $G(m)$, $m\geq 3$, which we then use to calculate asymptotics for the conjugacy growth of $G(m)$, and show that the conjugacy growth series of $G(m)$ with respect to the `free product' generating set $\{x, y\}$ is transcendental. We prove two additional properties of $G(m)$ that connect to conjugacy, namely that the permutation conjugator length function is constant, and that the falsification by fellow traveler property (FFTP) holds with respect to $\{x, y\}$. These imply that the language of all conjugacy geodesics in $G(m)$ with respect to $\{x, y\}$ is regular.