The equivalence of deterministic gsm replications on Q-rational languages is decidable

From MaRDI portal





It is shown that two deterministic gsm replications \(\tau_ 1\) and \(\tau_ 2\) are equivalent on the support L of a Q-rational formal power series if and only if \(\tau_ 1(w)=\tau_ 2(w)\) for all w in L such that the length of w does not exceed a certain bound which depends only on the numbers of states in the deterministic gsm's involved and on the size of the matrix system accepting L. Application of this result to the deterministic gsm equivalence problem improves known bounds. Finally, sufficient conditions for an arbitrary family of languages to have a decidable deterministic gsm replication equivalence problem are presented.











This page was built for publication: The equivalence of deterministic gsm replications on Q-rational languages is decidable

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