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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4041314
Language Label Description Also known as
default for all languages
No label defined
    English
    The equivalence of deterministic gsm replications on Q-rational languages is decidable
    scientific article; zbMATH DE number 4041314

      Statements

      The equivalence of deterministic gsm replications onQ-rational languages is decidable (English)
      0 references
      The equivalence of deterministic gsm replications on Q-rational languages is decidable (English)
      0 references
      1987
      0 references
      generalized sequential machine
      0 references
      Q-rational languages
      0 references
      decidability
      0 references
      deterministic gsm replications
      0 references
      formal power series
      0 references
      equivalence
      0 references
      0 references
      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.
      0 references

      Identifiers