The equivalence of deterministic gsm replications on Q-rational languages is decidable
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.
- 2DST mappings of languages and related problems
- AFL with the semilinear property
- Generalized Automata and Stochastic Languages
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- On some transducer equivalence problems for families of languages
- One way finite visit automata
- Reset machines
- Syntactic operators on full semiAFLs
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)