Efficient solution of some problems in free partially commutative monoids

DOI10.1016/0890-5401(90)90010-FMaRDI QIDQ2640345zbMATH OpenFDO

Publication date 1990

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(90)90010-F

commutation monoids linear-time algorithms partial commutativity traces

Semigroups in automata theory, linguistics, etc. (20M35) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Review text

A partially commutative alphabet is a pair (\(\Sigma\),\(\theta\)) consisting of a finite alphabet \(\Sigma\) and a binary relation \(\theta\) in \(\Sigma\) which gives the pairs of commuting letters. The free partially commutative monoid M(\(\Sigma\),\(\theta\)) determined by (\(\Sigma\),\(\theta\)) is the quotient monoid \(\Sigma^*/\equiv\), where \(\equiv\) is the congruence generated by \(\theta\). The authors present and analyze linear-time algorithms for several basic combinatorial problems concerning such monoids. In the following brief descriptions of the main questions considered, a fixed monoid M(\(\Sigma\),\(\theta\)) is assumed. (1) A nonempty word \(y\) is primitive mod \(\theta\), if there is no word \(z\) such that \(y\equiv z^{k}\) for some \(k>1\). If \(x\equiv y^{n}\) and \(y\) is primitive mod \(\theta\), then \(y\) is a congruential root of \(x\). Such a root can be found in time linear in the length of \(x\). Also, the related question whether two given words have some \(\equiv\)-congruent powers can be answered in linear time. (2) The generalized pattern-matching problem asks whether a word \(y\) is congruent to a factor of another given word \(x\). For this problem a linear-time algorithm which makes use of the Knuth-Morris-Pratt algorithm is given. (3) Two words \(x\) and \(y\) are conjugate in the free monoid \(\Sigma^*\) if \(xz = zy\) for some word \(z\), or equivalently, if there are words \(u\) and \(v\) such that \(x = uv\) and \(y = vu\). In the more general case at hand, these two definitions lead to different concepts, but for both of them linear-time algorithms deciding conjugacy are given. The paper is very well written and the extensive background knowledge used in the algorithms is also clearly presented.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Efficient solution of some problems in free partially commutative monoids

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