Литература

• [AHU] Aho A., Hopcroft J., Ullman J. The design and analysis of computer algorithms.- Reading: Addison-Wesley, 1974. [Имеется перевод. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.]
• [AU] Aho A., Ullman J. The theory of parsing, translation and compiling. I-II.- Englewood Cliffs: Prentice-Hall, 1972-1974. [Имеется перевод: Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах.- М.: Мир, 1978.]
• [Bel] Berstel J. Sur les mots sans carre definis par un morphisme.- In: Springer Lecture Notes in Computer Science, vol. 71, 1979, p. 16-25.
• [Be2] Berstel J. Mots sans carre et morphismes iteres.- Universite Paris 7, Institute de Programmation, 1978, p. 78-42.
• [Be3] Berstel J. Transductions and context-free languages.- Stuttgart: B. G. Teubner, 1979.
• [Bo] Book R. Formal language theory and theoretical computer science.- Springer Lecture Notes in Computer Science, vol. 33, 1975, p. 1-15.
• [BoB] Book R., Brandenburg F. J. Representing complexity classes by equality sets.- Springer Lecture Notes in Computer Science, vol. 71, 1979, p. 49-57.
• [Ch] Chomsky N. Three models for the description of language.- IRE Trans. Informat. Theory, 1956, v. IT-2, p. 113-124. [Имеется перевод: Хомский Н. Три модели описания языка.- В кн.: Кибернетический сборник. Вып. 2.- М.: ИЛ, 1961, с. 237-266.]
• [ChS] Chomsky N., Schutzenberger M. P The algebraic theory of context-free languages.- In: Computer programming and formal systems. Ed. by P. Braffort and D. Hirschberg.- Amsterdam: North Holland, 1963, p. 118-161. [Имеется перевод: Хомский Н., Шютценберже М. П. Алгебраическая теория контекстно-свободных языков.- В кн.: Кибернетический сборник. Новая серия. Вып. 3.- М.: Мир, 1966, с. 195-242.]
• [CrG] Cremers A., Ginsburg S. Context-free grammar forms.- J. Cornput. System Sci., 1975, v. 11, p. 86-116.
• [Cu] Culik K. II. A purely homomorphic characterization of recursively enumerable sets.- J. Associat. Comput. Machinery, 1979, v. 26, p. 345-350.
• [CuF] Culik K. II, Fris I. The decidability of the equivalence problem for DOL-systems.- Information and Control, 1977, v. 35, p. 20-39.
• [CuK] Culik K. II, Karhumaki J. On the equality sets for homomorphisms on free monoids with two generators.- R. A. I. R. 0. Informat. theor., 1980, v. 14, p. 349-369.
• [CuM] Culik K. II, Maurer H. On simple representations of language families.- R. A. I. R. O. Informat. theor., 1979, t. 13, p. 241-250.
• [CuSl] Culik K. II, Salomaa A. On the decidability of homomorphism equivalence for languages.- J. Comput. System Sci., 1978, v. 17, p. 163-175.
• [De] Dejean F. Sur un theoreme de Thue.- J. Combinatorial Theory (A), 1972, v. 13, p. 90-99.
• [DeS] Dejean F., Schutzenberger M. P. On a question of Eggan.- Information and Control, 1966, v. 9, p. 23-25.
• [EhR1] Ehrenfeucht A., Rozenberg G. Simplifications of homomorphisms.- Information and Control, 1978, v. 38, p. 298-309.
• [EhR2] Ehrenfeucht A., Rozenberg G. Elementary homomorphisms and a solution of the DOL sequence equivalence problem.- Theoret. Comput. Sci., 1978, v. 7, p. 169-183.
• [EhR3] Ehrenfeucht A., Rozenberg G. On a bound for the DOL sequence equivalence problem.- Theor. Comput. Sci., 1980, v. 12, p. 339-342.
• [EhR4] Ehrenfeucht A., Rozenberg G. On the subword complexity of square-free DOL languages.- Theoret. Comput. Sci., 1981, v. 16, no. 1, p. 25-32.
• [Ei] Eilenberg S. Automata, languages and machines. Vol. A.- New York: Academic Press, 1974.
• [EnR] Engelfriet J., Rozenberg G. Fixed point languages, equality languages and representation of recursively enumerable languages.- J. Associat. Comput. Machinery, 1980, v. 27, p. 499-518.
• [G1] Ginsburg S. The mathematical theory of context-free languages.- New York: McGraw-Hill, 1966. [Имеется перевод: Гинзбург С. Математическая теория контекстно-свободных языков.- М.: Мир, 1970.]
• [G2] Ginsburg S. Algebraic and automata-theoretic properties of formal languages.- Amsterdam: North Holland, 1975.
• [GR] Ginsburg S., Rice H. Two families of languages related to AL- GOL.- J. Associat. Comput. Machinery, 1962, v. 9, p. 350-371. [Имеется перевод: Гинзбург С, Райе X. Два класса языков типа АЛГОЛ.- В кн.: Кибернетический сборник. Новая серия. Вып. 6.- М.: Мир, 1969, с. 184-214.]
• [Gr1] Greibach S. A new normal form theorem for context-free phrase structure grammars.- J. Associat. Comput. Machinery, 1965, v. 12, p. 42-52.
• [Gr2] Greibach S. The hardest context-free language.- S. I. A. M. J. Comput., 1973, v. 2, p. 304-310.
• [H] Hall M., Jr. Generators and relations in groups - the Burnside problem.- In: Lectures on modern mathematics. Ed by T. L. Saaty. Vol. II.- New York: Wiley and Sons, 1964, p. 42-92.
• [Har] Harrison M. Introduction to formal language theory.- Reading Addison-Wesley, 1978.
• [Has] Hashiguchi K. A decision procedure for the order of regular events.- Theoret Comput. Sci, 1979, v. 8, p. 69-72.
• [HU] Hopcroft J., Ullman J. Introduction to automata theory. Langua- ges and computation.- Reading: Addison-Wesley, 1979.
• [KaS] Karhumaki J., Simon I. A note on elementary homomorphisms and the regularity of equality sets.- E. A. T. C. S. Bulletin, 1979.
• [K1] Kleene S. C. Representation of events in nerve nets and finite automata.- In: Automata studies.- Princeton: Princeton Univ. Press, 1956. [Имеется перевод: Клини С. К. Представление событий в нервных сетях и конечные автоматы.- В кн.: Автоматы.- М.: ИЛ, 1956, с. 15-67.
• [La] Lallement G. Semigroups and combinatorial applications.- New York: Wiley and Sons, 1979. [Имеется перевод: Лаллеман Ж. Полугруппы и комбинаторные приложения.- М.: Мир, 1985.
• [Le] Lecerf Y. Recursive insolubilite de l'equation generale de diago nalisation de deux monomorphismes de monoides libres φx = ψx.- C. R. Acad. Sci. Paris, 1963. t. 257, p. 2940-2943.
• [L] Lindenmayer A. Mathematical models for cellular interaction in development. I-II.- J. Theoret. Biology, 1968, v. 18, p. 280-315.
• [Li1] Linna M. Finite powei pioperty of regular languages.- In: Automata. Languages and programming. Ed. by M. Nivat.- Amsterdam: North Holland, 1973, p. 87-98.
• [Li2] Linna M. The DOL-ness for context-free languages is decidable.- Information Processing Letters, 1976, v. 5, p. 149-151.
• [Li3] Linna M. The decidability of the DOL prefix problem.- Internat. J. Comput. Math., 1977, v. 6, p. 127-142.
• [LyS] Lyndon R., Schutzenberger M. P. The equation a^M = b^Nc^P in a free group.- Michigan Math. J., 1962, v. 9, p. 289-298.
• [ManS] Mandel A., Simon I. On finite semigroups of matrices.- Theoret. Comput. Sci., 1978, v. 5, p 101-111.
• [Map1] Марков А. А. Условия полноты для неравномерных кодов.- В кн.: Проблемы кибернетики. Вып. 9.- М.: Физматгиз, 1963, с. 327-331.
• [Mau] Maurer H. Theoretische Grundlagen der Programmiersprachen.- Mannheim: Bibliographisches Institut, 1969.
• [MSW1] Maurer H., Salomaa A., Wood D. On generators and generative capacity of EOL forms.- Acta Informatica, 1980, v. 13, p. 87-107.
• [MSW2] Maurer H., Salomaa A., Wood D. Context-free grammar forms with strict interpretations.- J. Comput. System Sci., 1980, v. 21, p. 110-135.
• [MSW3] Maurer H., Salomaa A., Wood D. Dense hierarchies of grammatical families.- J. Ass. Comput. Machin., 1982, v. 29, p. 118-126.
• [MSW4] Maurer H., Salomaa A., Wood D. Colorings and interpretations: a connection between graphs and grammar forms.- Discr. Appl. Math., 1981, v. 3, p. 119-135.
• [Mc] McLean D. Idempotent semigroups.- Amer. Math. Monthly, 1954, v. 61, p. 110-113.
• [McP] McNaughton R., Papert S. Counter-free automata.- Cambridge: M. I. T. Press, 1971.
• [MiS] Morisaki M., Sakai K. A complete axiom system for rational sets with multiplicity.- Theoret. Comput. Sci, 1980, v. 11, p. 79-92.
• [MoH1] Morse M., Hedlund G. Symbolic dynamics.- Amer. J. Math, 1938, v. 60, p. 815-866.
• [MoH2] Morse M, Hedlund G. Unending chess, symbolic dynamics, and a problem in semigroups - Duke Math. J., 1944, v. 11, p. 1-7.
• [Nie] Nielsen M. On the decidability of some equivalence problems for DOL systems - Information and Control, 1974. v. 25, p. 166-193.
• [Niv] Nivat M. Transductions des langages de Chomsky.- Ann. Inst. Fourier, Grenoble, 1968, t. 18, p. 339-456.
• [P] Post E. A variant of a recursively unsolvable problem.- Bull. Americ. Math. Soc, 1946, v. 52, p. 264-268.
• [RS] Rozenberg G, Salomaa A. The mathematical theory of L systems.- New York: Academic Press, 1980.
• [Ru1] Ruohonen K. The decidability of the FOL-DOL equivalence problem.- Information Processing Letters, 1979, v. 8, p. 257-260.
• [Ru2] Ruohonen K. The inclusion problem for DOL languages.- Elektronische Informationsverarbeitung und Kvbernetik, 1980, Bd 15, S. 535-548.
• [Sa1] Salomaa A. Theory of automata.- Oxford - Pergamon Press, 1969.
• [Sa2] Salomaa A. Formal languages - New York' Academic Press. 1973.
• [Sa3] Salomaa A. On sentential forms of context-free grammars.- Acta Informatica, 1973, v. 2, p. 40-49.
• [Sa4] Salomaa A. Comparative decision problems between sequential and parallel rewriting.- In: Proc. Symp. Uniformly Structured Automata and Logic, Tokyo, 1975, p. 62-66.
• [Sa5] Salomaa A. Equality sets for homomorphisms of free monoids.- Acta Cybernetica, 1978, v. 4, p. 127-139.
• [Sa1S] Salomaa A, Soittola M. Automata-theoretic aspects of formal power series.- Berlin: Springer, 1978 [SarP] Sardinas A, Patterson G. A necessary and sufficient condition for the unique decomposition of coded messages.- IRE Intern. Conv. Record, 1953, v. 8, p. 104-108. [Имеется перевод: Сардинас А, Паттерсон Дж. Необходимое и достаточное условие однозначного разложения закодированных сообщений.- В кн.: Кибернетический сборник. Вып. 3.- М.: ИЛ, 1961, с. 93-102.]
• [Sh] Shamir E. A representation theorem for algebraic and context- free power series in noncommuting variables.- Information and Control, 1967, v. 11, p. 239-254.
• [St] Stanat D. A homomorphism theorem for weighted context-free grammars.- J. Comput. System Sci, 1972, v. 6, p. 217-232.
• [T1] Thue A. Ober unendliche Zeichenreihen.- Videnskapsselskapets Skrifter. I. Mat.- naturv. Klasse, Kristiania, 1906.
• [T2] Thue A. Ober die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.- Videnskapsselskapets Skrifter. I. Mat.- naturv. Klasse, Kristiania, 1912.
• [W] Wood D. Grammar and L forms: an introduction.- Berlin: Springer, 1980.