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.8183544874191284
0 references
0.7632793188095093
0 references
0.7612719535827637
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