92.Korenjak A.J., Hopcroft J.E. Simple deterministic languages IEEE Conf. Record of 7th Annual Symposium on Switching and Automata Theory. 1966. P. 36-46. (Русский перевод: Кореньяк А., Хопкрофт Дж. Простые детерминированные языки Сб. "Языки и автоматы". 1975. С. 71-96.)

93.Lallement G. Semigroups and combinatorial applications. N.Y. 1979. (Русский перевод: Лаллеман Ж. Полугруппы и комбинаторные приложения. М. 1985.)

94.Lee EunYung, Choe KwangMeo. Grammar coverings of a deterministic parser with action conflicts Inf. Process. Lett. 1994. V. 51. N 2. P. 85-92.

95.Levy J.P. Automatic correction of syntax errors in programming languages

Acta Informatica. 1975. N 4. P.271-292.

96.McWhirter I.P. Substitution expressions J. Comput. System Sci. 1971. V. 5. P. 629-637. (Русский перевод: МакВертер И.П. Подстановочные выражения Кибернетический сб. Н. С. 1973. Вып. 10. С. 127-136.)

97.Melnikov B. The equality condition for infinite catenations of two sets of finite words Int. J. of Found. of Comp. Sci. 1993. V. 4. N 3. P. 267-274.

98.Melnikov B.F., Vakhitova A.A. Some more on the finite automata Korean Journal of Computational and Applied Mathematics. 1998. V. 5. No. 3. P. 495505.

99.Nepomnjashchaja A.Sh. Decidability of the equivalence problem for synchronous deterministic pushdown automata Lect. Notes Comput. Sci. 1984. V. 176. P.

425-432.

100.Newell A., Shaw J.C. Programming the logic theory machine Proc. Western

Joint Computer Conf. 1957. P. 230-240.

101.Oettinger A. Automatic syntactic analysis and the pushdown store Structure of Language and its Mathematimathcal Concepts : Proc. 12th Symposium on

Applied Mathematics. 1961. P. 104-129.

102.Ore O. Theory of graphs. 1962. (Русский перевод: Оре О. Теория графов. М.

103.Oyamaguchi M. The equivalence problem for realtime DPDAs J. ACM.

1987. V. 34. N 3. P. 731-760.

104.Pair C. Arbres, piles et compilation RFTI - Chiffres. 1964. V. 7. N 3. P.

199-216.

105.Post E.L. Recursive unsolvability of a problem of Thue J. Symb. Logic. 1947.

V. 12. P. 1-11.

106.Ruohonen K. On some variants of Posts correspondence problem Acta Inf.

1983. V. 19. N 4. P. 357-362.

107.Salomaa A. Jewels of formal language theory. Rockville. 1981. (Русский пере вод: Саломаа А. Жемчужины теории формальных языков. М. 1986.)

108.Salomaa K., Wood D., Yu Sh. Pumping and pushdown machines Inf. Theor.

et Appl. 1994. V. 28. N 3-4. P. 221-232.

109.Schutzenberger M.P. On contextfree languages and pushdown automata

Inform. and Control. 1963. V. 6. N 3. P. 246-264.

110.Senizergues G. The equivalence problem for deterministic pushdown automata is decidable Lecture Notes in Computer Science. 1997. V. 1256. P. 671-681.

111.Shankar P., Adiga B.S. A graphbased regularity test for deterministic context-free languages Theoretimathcal Computer Science. 1991. V. 88. P. 117-125.

112.Shankar P., Adiga B.S. A graphbased regularity test for deterministic context-free languages Theoretimathcal Computer Science. 1992. V. 95. P. 339-340.

113.Stanevichene L.I. A new method for the description of deterministic languages Proc. of the 14th International Symp. "INFORMATICA". Yugoslavia, 1979. P. 113-116

114.Stanevichene L.I. On an approach in context free language theory Proc. of the Second International Conf. "Current Problems of Fundamental Sciences". V.

6. M. 1994. P. 321-324.

115.Stanevichene L.I. On the Equivalence of Pushdown Automaton Vertices Third International Conference of WomenMathematicians. Abstracts. Voronezh, 1995.

116.Stanevichene L.I. DGraphs in ContextFree Language Theory Informatica (journal of Lithuanian Academy of Sciences). 1997. V. 8. No. 1. P. 13-26.

117.Stanevichene L.I., Choban V.B. On a Subclass of Deterministic Pushdown Automata Proc. of Intern. Congr. of the Association "Women Mathema ticians". Moscow-Puschino, May 30-June 3, 1994. N.Novgorod, 1994. Issue

3. P. 31-35.

118.Stanevichene L.I., Vylitok A.A. An algorithm for transformation of finite automata to regular expressions Informatica. 2000. V. 11. No. 1. P. 49-54.

119.Stearns R.E. A regularity test for pushdown machines Inform. and Control. 1967. V. 11. N 3. P. 323-340. (Русский перевод: Стирнз Р. Проверка регулярности для магазинных автоматов Кибернетический сб. Н. С. 1971. Вып. 8.

С. 117-139.)

120.Sudkamp Th.A. Languages and machines - An introduction to the theory of computer science, Second edition. AddisonWesley, Reading, Mass. 1997.

121.Tomita E., Seino K. The extended equivalence problem for a class of nonreal-time deterministic pushdown automata Acta Informatica. 1995. V. 32. P.

395-413.

122.Valiant L.G. Decision procedures for families of deterministic pushdown automata Univ. of Warwick Computer Centre Report. 1973. N 7.

123.Valiant L.G. The equivalence problem for deterministic finite turn pushdown

automata Inform. and Control. 1974. N 2. P. 123-133.

124.Valiant L.G. Regularity and related problems for deterministic pushdown

automata J. Assoc. Comput. Mach. 1975. V. 22. P. 1-10.

125.Walters D.A. Deterministic context sensitive languages Inform. and Control.

1970. V. 17. N 1. P.14-61.

126.Wirth N. The programming language PASCAL Acta Informatica. 1971. 1.1.

P. 35-63.

127.Wirth N., Weber H. EULER - a generalization of ALGOL and its formal definition : Parts 1 and 2 Comm. ACM. V. 9. N 1. P. 13-23. V. 9. N 2. P. 89-99.

128.Yair I., Amiram Y. New families of non real time DPDAs and their decidability results Theor. Comput. Sci. 1984. V. 34. N 3. P. 255-274.

129.Yntema M.K. Inclusion Relations among Families of ContextFree Languages Information and Control. 1967. V. 10. P.572-597.

СЛОВАРЬ ТЕРМИНОВ

алфавит (alphabet)

входной (input)

магазинный (pushdown) биребро (biarc) вершина (vertex)

бесполезная (useless)

дуги Dграфа

конечная (terminal)

начальная (initial)

D графа

входная (input)

заключительная (final)

дуги магазинного автомата

магазинного автомата

маршрута магазинного автомата

промежуточная (intermediate)

вывод реализует соотношение (a derivation realizes the correlation) x ==* y вычеркивание (deletion) вычисление (computation) глубина (depth)

структуры (of a structure)

цепочки Dязыка (of a Dword) гнездо (nest)

простое (simple) граф

магазинного автомата (graph of a pushdown acceptor)

обобщенный (extended)

сопряжений (team graph) длина родословной маршрута (length of a genealogy of a computing sequence) дуга (edge)

бесполезная (useless)

каркасная (skeleton)

магазинного автомата

соединимая (joined)

стирающая (deleting)

D графа заряд (charge)