Transductions and the parallel generation of languages^†

^†This research was supported by the National Sciences and Engineering Council of Canada under grant No. A-7403 and by the National Science Foundation of the United States of America under grant MCS-8003348.

Abstract

Each regular expression R over a finite vocabulary P of appropriately chosen ordered pairs provides a type of parallel rewriting scheme here called an RL scheme. The traditional IL schemes (resp., TIL schemes) are identified with certain RL schemes for which R is a strictly locally testable language (resp., a finite union of strictly locally testable languages). Using the virtual identity of RL schemes with a-transducers, a collection of decision procedures are imported into L theory from the theory of a-transducers. A collection of undecidability results for RL theory are proved by simulating Post tag systems with RL systems.

Concepts of determinism are defined for RL schemes and systems. Determinism is shown to be decidable for RL schemes butnot for RL systems. Equivalence is shown to be decidable for deterministic RL schemes.

Keywords:

• Parallel Rewriting
• L-Systems
• Finite Transducers
• Decidability
• Global Context

^†This research was supported by the National Sciences and Engineering Council of Canada under grant No. A-7403 and by the National Science Foundation of the United States of America under grant MCS-8003348.

^†This research was supported by the National Sciences and Engineering Council of Canada under grant No. A-7403 and by the National Science Foundation of the United States of America under grant MCS-8003348.

Notes

^†This research was supported by the National Sciences and Engineering Council of Canada under grant No. A-7403 and by the National Science Foundation of the United States of America under grant MCS-8003348.