Automata and partial commutations

From MaRDI portal





We consider words over an alphabet equipped with a partial commutation rule. The main result of the paper gives a sufficient condition for a set of words closed under the commutation rule to be recognizable by a finite automaton. More precisely, if \(X\) is recognizable and if \(ab\sim ba\) implies that the letters \(a\) and \(b\) do not appear in the same word of \(X\), then the closure of \(X^*\) under the commutation rule is recognizable.




Cited in
(86)








This page was built for publication: Automata and partial commutations

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