𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The undecidability of some equivalence problems concerning ngsm's and finite substitutions

✍ Scribed by P. Turakainen

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
437 KB
Volume
174
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown to be undecidable whether an c-free finite substitution and a two-state simple E-free ngsm are equivalent on {a, b}*. Consequently, the state-minimization of such ngsm's and the nonterminal-minimization of linear grammars having two nonterminals are undecidable.

Applications to some other decision problems concerning E-free finite substitutions and linear grammars are also given. Finally it is shown that the time-equivalence problem is undecidable for propagating OL systems, i.e., for iterated c-free finite substitutions. This solves an open problem presented in [4].

πŸ“œ SIMILAR VOLUMES

Some problems concerning the assessment
Some problems concerning the assessment of arterial prosthetic materials
✍ Wesolowski, Sigmund A. πŸ“‚ Article πŸ“… 1967 πŸ› John Wiley and Sons 🌐 English βš– 214 KB

## NOTE T 'OI,. 1 (1967) \* This work was aided by grants-in-aid from t~he USPHG and the Research The two points a t which moral issues arise in reasonable clinical action are: Conncil of tbe City of New York.