Formal schemes for language translations
- 1 January 1972
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 3 (1-4) , 17-48
- https://doi.org/10.1080/00207167108803049
Abstract
In this paper a number of formal schemes for recognizing or generating of translations(binary relations on words)are studied, most of them already being known. Known results are surveyed and new results are obtained on their interrelationships, closure properties, compositions and the preservation of families of languages under such schemes. For various recognizing schemes(transducers)the equivalent generative schemes(generalized grammars)are exhibited. Also, the equivalence of many generative schemes is shown.Keywords
This publication has 11 references indexed in Scilit:
- Properties of syntax directed translationsJournal of Computer and System Sciences, 1969
- Syntax directed translations and the pushdown assemblerJournal of Computer and System Sciences, 1969
- Syntax-Directed TransductionJournal of the ACM, 1968
- A note on preservation of languages by transducersInformation and Control, 1968
- Multitape one-way nonwriting automataJournal of Computer and System Sciences, 1968
- One-way stack automataJournal of the ACM, 1967
- Preservation of languages by transducersInformation and Control, 1966
- On Relations Defined by Generalized Finite AutomataIBM Journal of Research and Development, 1965
- Classes of languages and linear-bounded automataInformation and Control, 1964
- Discontinuity and asymmetry in phrase structure grammarsInformation and Control, 1963