The decidability of a mapping problem for generalized sequential machines with final states

✍ Scribed by Kenneth B. Salomon

• Publisher: Elsevier Science
• Year: 1975
• Tongue: English
• Weight: 947 KB
• Volume: 10
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(75)80040-7

✦ Synopsis

The following problem is shown to be decidable for arbitrary regular sets R i and Rz : Does there exist a generalized sequential machine with final states which maps R 1 onto R2 ? In the development of the solution a graphical interpretation of bounded and unbounded regular sets is presented. Also, the subproblem when Ri and R~ are arbitrary bounded regular sets is shown to be decidable.