J. Engelfriet
- 1 Atxo, A.V. Indexed grammars--an extension of context-free grammars. J. ACM 15, 4 (Oct. 1968), 647- 671. Google Scholar
- 2 AHO, A.V., AND ULLMAN, J.n. A characterization of two-way deterministic classes of languages. ~ Comptr. Syst. Sci. d (1970), 523-538.Google Scholar
- 3 BAKER, B.S., AND BOOK, R.V. Reversal-bounded muhipushdown machines. ~ Comptr. SyJt. Sci. 8 (1974), 315-332.Google Scholar
- 4 BOOK, R.V., GRE1BACH, S.A., AND WRATHALL, C. Comparisons and reset machines. Proc 5th Int. Colloq. on Automata, Languages, and Programming, Lecture Notes in Computer Science 62, SpringevVerlag, Berlin, 1978, pp. 113-124. Google Scholar
- 5 CLARK, K.L,, AND COWELL, D.F. Programs. Machines and Computation. McGraw-Hill, London, 1976.Google Scholar
- 6 CULIK, K. II. A purely homomorphic characterization of recursively enumerable sets. d.4 CM 26, 2 (April 1979), 345-350. Google Scholar
- 7 CULIK, K. II. Some decidability results about regular and pushdown translations. Inform. Proe. Laters 8 (1979), 5-8.Google Scholar
- 8 CULIK, K. II, AND Fats, I. The decidability of the equivalence problem for D0L systems. Inform. and Control 35 (1977), 20-39.Google Scholar
- 9 CULm, K. 11, AND SALOMAA, A, On the decidability of homomorphism equivalence for languages. J. Comptr. Syst. Sci. 17(1978), 163-175.Google Scholar
- 10 EHRENFEUCHT, A., AND ROZENBERG, G. Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comptr. Sci. 7 (1978), 169-184.Google Scholar
- 11 , EILENBERG, S. Automata, Languages, and Machines, Vol. `4. Academic Press, New York, 1974. Google Scholar
- 12 ENGELFRIET, J., AND ROZENBERG, G. Equality languages and fixed point languages. Inform. and Control 43 (1979), 20-49.Google Scholar
- 13 FISCHER, M.J. Grammars with macro-like productions. Ph.D. Th., Harvard U., Boston, Mass., 1968.Google Scholar
- 14 FISHER, G.A., AND RANEY, G.N. On the representation of formal languages using automata on networks. IEEE Conf. Rec. 10th Ann. Syrup. Switching and Automata Theory, Waterloo, Ontario, Canada, 1969, 157- 165.Google Scholar
- 15 GINSaURG, S. `41gebraicand`4utomata-TheoreticPropertiesofFormalLanguages. North-Holland/American Elsevier, Amsterdam/New York, 1975. Google Scholar
- 16 G1NSBURG, S., GREIBACH, S.A., AND HARRISON, M.A. Stack automata and compiling. J.4CM 14, I (Jan. 1967), 172-201. Google Scholar
- 17 GzNsauR~, S., AND ROSE, G.F. Preservation of languages by transducers. Inform. and Control 9 (1966), 153-176. See also: GINSBURG, S., AND ROSE, G.F. A note on preservation of languages by transducers. Inform. and Control 12 (1968), 549-552.Google Scholar
- 18 GINSBURG, S., AND SPANJER, E.H. Finite-turn pushdown automata. SIAMJ. Control 4 (1966L 429--453.Google Scholar
- 19 GOLDSTINE, J. Automata with data storage. Proc. Conf. Theoret. Comptr. Sci., University of Waterloo, Waterloo, Ontario, 1977, pp.239-246.Google Scholar
- 20 GREIBACH, S.A. The hardest context-free language. SIAMJ. Comptg. 2 (1973), 304-310.Google Scholar
- 21 GREIBACH, S.A. Visits, crosses, and reversals for nondeterministic off-line machines. Inform. and Control 36 (1978), 174-216.Google Scholar
- 22 GRIFF1THS, T.V. Some remarks on derivations in general rewriting systems. Inform. and Control 12 (1968), 27-54.Google Scholar
- 23 HARTMANIS, J. Context-free languages and Turing machine computations. In Mathematical Aspects of Computer Science, Vol. 19: Proc. Syrup. `4pplied Mathematics, J.T. Schwartz, Ed., American Mathematical Society, Providence, R.I., 1967, pp. 42-51.Google Scholar
- 24 HARTMANIS, J., AND HOPCROFT, J.E. What makes some language theory problems undecidable? J. Comptr. Syst. Sci. 4 (1970), 368-376.Google Scholar
- 25 HERMAN, G.T., ^ND WALKER, A. Context-free languages in biological systems. Int. J. Comptr. Math. 4 (1975), 369-391.Google Scholar
- 26 HERMAN, G.T., AND WALKER, A. On the stability of some biological schemes with cellular interactions. Theoret. Comptr. Sci. 2 (1976), 115-130.Google Scholar
- 27 KORENJAK, A.J., AND HOPCROEL J.E. Simple deterministic languages. 1EEE 7th Ann. Syrup. Switching and Automata Theory, Berkeley, Calif., 1966, pp. 36-46.Google Scholar
- 28 MINSK~, M. Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, New Jersey, 1967. Google Scholar
- 29 NIvA'r, M. Transductions des langages de Chomsky. Ann. Inst. Fourier 18, I (1968), 339-456, Grenoble.Google Scholar
- 30 ROSENBERG, A.L. On multi-bead finite automata. IBM J. Res. DeveL 10 (~966), 388-394. Google Scholar
- 31 SALOMAA, A. Equality sets for homomorphisms of free monoids. To appear in Acta Cybernetica.Google Scholar
- 32 SALOMAA, A. Formal Languages. Academic Press, New York, 1973. Google Scholar
- 33 S^vrrcn, W.J. How to make arbitrary grammars look like context-free grammars. SIAM J. Comptg. 2 (1973), 174-182.Google Scholar
- 34 VIT,~NYI, P.M.B., ANt) SAVITCa, W.J. On inverse deterministic pushdown transductions. J. Comptr. Syst. Sci. 16 (1978), 423-444.Google Scholar
Index Terms
- Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
Recommendations
Languages as libraries
PLDI '11Programming language design benefits from constructs for extending the syntax and semantics of a host language. While C's string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage ...
Languages as libraries
PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and ImplementationProgramming language design benefits from constructs for extending the syntax and semantics of a host language. While C's string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage ...
On characterizations of recursively enumerable languages
Geffert has shown that earch recursively enumerable language L over Σ can be expressed in the form L { h(x) 1 g(x) x in Δ +} Σ * where Δ is an alphabet and g, h is a pair of morphisms. Our purpose is to give a simple proof for ...
Comments