Characterizations of transductions defined by abstract families of transducers. (English) Zbl 0221.94077


68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI


[1] A. V. Aho, J. E. Hopcroft, andJ. D. Ullman, A general theory of translations,Math. Systems Theory 3 (1969), 193–221. · Zbl 0175.00803 · doi:10.1007/BF01703920
[2] A. V. Aho andJ. D. Ullman, A characterization of two-way deterministic classes of languages,IEEE Conference Record of 1969 Tenth Annual Symposium on Switching Automata Theory, pp. 231–239. · Zbl 0222.68034
[3] W. J. Chandler, Abstract families of deterministic languages,Proc. ACM Symposium on Theory of Computing, pp. 21–30, Marina del Rey, California, 1969. · Zbl 1282.68153
[4] J. E. Hopcroft andJ. D. Ullman, An approach to a unified theory of automata,Bell System Tech. J. 46 (1967), 1793–1829. · Zbl 0155.34303
[5] C. C. Elgot andJ. E. Mezei, On relations defined by generalized finite automata,IBM J. Res. Develop. 9 (1965), 47–68. · Zbl 0135.00704 · doi:10.1147/rd.91.0047
[6] S. Ginsburg,The Mathematical Theory of Context-free Languages, McGraw-Hill, New York, 1966. · Zbl 0184.28401
[7] S. Ginsburg andS. A. Greibach, Abstract families of languages,IEEE Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, pp. 128–139.
[8] S. Ginsburg, S. A. Greibach andM. A. Harrison, One-way stack automata.J. Assoc. Comput. Mach. 14 (1967), 339–418. · Zbl 0171.14803
[9] S. Ginsburg andG. Rose, Operations which preserve definability in languages,J. Assoc. Comput. Mach. 10 (1963), 175–195. · Zbl 0192.07201
[10] S. Ginsburg andG. Rose, Preservation of languages by transducers,Information and Control 9 (1966), 153–176. · Zbl 0186.01301 · doi:10.1016/S0019-9958(66)90211-7
[11] S. A. Greibach, An infinite hierarchy of context-free languages,J. Assoc. Comput. Mach. 16 (1969), 91–106. · Zbl 0182.02002
[12] M. A. Harrison andO. H. Ibarra, Multi-tape and multi-head pushdown automata,Information and Control 13 (1968), 433–470. · Zbl 0174.02701 · doi:10.1016/S0019-9958(68)90901-7
[13] O. H. Ibarra, Generalizations of pushdown automata. Ph.D. Thesis, University of California, Berkeley, 1967. · Zbl 0166.26601
[14] M. O. Rabin andD. Scott, Finite automata and their decision problems,IBM J. Res. Develop. 3 (1959), 114–125. · doi:10.1147/rd.32.0114
[15] A. L. Rosenberg, Nonwriting extensions of finite automata. Ph.D. Thesis, Harvard University, 1965.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.