maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-2-176-196mais-239Research ArticleОригинальные статьиArticlesМП-автоматы с независимыми счётчикамиPDA with Independent CountersДехтярьМихаил ИосифовичDekhtyarMichael

д-р физ.-мат. наук, доцент, 170000 Россия, г. Тверь, ул. Желябова, 33

д-р физ.-мат. наук, доцент, Zhelyabova str., 33, Tver, Russia, 170000

Michael.Dekhtyar@tversu.ruКарловБорис НиколаевичKarlovBoris

канд. физ.-мат. наук, 170000 Россия, г. Тверь, ул. Желябова, 33

канд. физ.-мат. наук, код, Zhelyabova str., 33, Tver, Russia, 170000

bnkarlov@gmail.comТверской государственный университетРоссияDept. of Computer Science, Tver State UniversityRussian Federation201520042015222176196Copyright © Дехтярь М.И., Карлов Б.Н., 20152015Дехтярь М.И., Карлов Б.Н.Dekhtyar M., Karlov B.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/239

Магазинные автоматы с независимыми счётчиками (МПНС) объединяют возможности МП-автоматов и сетей Петри. Они были предложены в работах [21, 15] как средство для распознавания языков, порождаемых категориальными грамматиками зависимостей (КГЗ). КГЗ представляют собой классические категориальные грамматики, расширенные ориентированными поляризованными валентностями. Они позволяют выразить как проективные, так и непроективные зависимости между словами предложения. МПНС — это обычный МП-автомат, к которому добавлено конечное число счётчиков. Независимость счётчиков означает, что их содержимое не влияет на выбор очередного действия автомата. В первой части статьи мы сравниваем несколько вариантов определения МПНС и доказываем эквивалентность двух вариантов МПНС: без синтаксических пустых циклов и без семантических пустых циклов. Отмечаем также некоторые связи между МПНС-языками и языками сетей Петри. Мы показываем, что МПНС эквивалентны стек+бэг МП- автоматам (СБМПА), предложенным независимо Сёгаардом (Søgaard), и что СБМПА без пустых циклов распознают в точности КГЗ-языки. Мультимодальные категориальные грамматики зависимостей (ммКГЗ) были введены в [4] как расширения КГЗ, позволяющие управлять пересечениями некоторых зависимостей. Класс ммКГЗ-языков достаточно богат и обладает многими свойствами замкнутости, в частности, он образует абстрактное семейство языков. Во второй части статьи мы расширяем МПНС и определяем МП-автоматы со стеками независимых счётчиков (МПСНС). Это расширение двоякое: (1) каждый счётчик представляет стек натуральных чисел и (2) добавляется функция, которая позволяет уменьшать число на вершине стека счётчика, только если вершины всех связанных с ним счётчиков равны нулю. Наш основной результат утверждает, что МПСНС допускают в точности класс ммКГЗ-языков.

Push-down automata with independent counters (PDACs) combine the power of PDAs and Petri Nets. They were developed in [21, 15], as a tool of recognition of languages generated by Categorial Dependency Grammars (CDGs). CDGs are classical categorial grammars extended by oriented polarized valencies. They express both projective and non-projective dependencies between the words of a sentence. PDAC is a usual PDA equipped with a finite number of counters. The independence of counters means that their state has no effect on the choice of an automaton move. In the first part of the paper we compare some variants of PDACs and prove the equivalence of two variants of PDAs with independent counters: without syntactic and without semantic ε-loops. Some connections between PDAC-languages and Petri Net languages are noticed. Then we show that PDACs are equivalent to stack+bag push-down automata (SBPA) independently introduced by Søgaard and that ε-acyclic SBPAs recognize exactly CDG-languages. Multimodal Categorial Dependency Grammars (mmCDGs) were introduced in [4] as an extension of GDGs that allows control of some intersections of dependencies. The class of mmCDG-languages is rich enough and has good closure properties, that it forms AFL. In the second part of the paper we extend PDACs and introduce push-down automata with stacks of independent counters (PDASC). PDASCs extend PDACs twofold: (i) each counter is a stack of integers and (ii) there is a restriction function which allows to diminish a head of a counter only if the heads of all dependent counters are zeros. Our main result says that these PDASCs accept exactly the class of mmCDG- languages. The article is published in the author’s wording.

автоматыформальные грамматики и языкимагазинные автоматы с независимыми счётчикамипроективная и непроективная зависимостькатегориальная грамматика зависимостеймультимодальная категориальная грамматика зависимостеймагазинные автоматы со стекамиautomataformal grammars and languagespush-down automata with independent countersprojective and non-projective dependencycategorial dependency grammarmultimodal categorial dependency grammarpush-down automata with stacks of independent counterRussian Foundation of Basic ResearchReferencesBar-Hillel Y., Gaifman H., Shamir E., “On categorial and phrase structure grammars”, Bull. Res. Council Israel, 9F (1960), 1–16.Bar-Hillel Y., Gaifman H., Shamir E., “On categorial and phrase structure grammars”, Bull. Res. Council Israel, 9F (1960), 1–16.Dekhtyar M., Dikovsky A., “Categorial dependency grammars”, Proc. of Int. Conf. on Categorial Grammars, 2004, 76–91.Dekhtyar M., Dikovsky A., “Categorial dependency grammars”, Proc. of Int. Conf. on Categorial Grammars, 2004, 76–91.Dekhtyar M., Dikovsky A., “Generalized categorial dependency grammars”, Pillars of Compute Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, LNCS, 4800, 2008, 230–255.Dekhtyar M., Dikovsky A., “Generalized categorial dependency grammars”, Pillars of Compute Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, LNCS, 4800, 2008, 230–255.Dekhtyar M., Dikovsky A., Karlov B., “Iterated dependencies and Kleene iteration”, Proc. of the 15th Conference on Formal Grammar (FG 2010), LNCS, 7395, Copenhagen, Denmark, 2012, 66–81.Dekhtyar M., Dikovsky A., Karlov B., “Iterated dependencies and Kleene iteration”, Proc. of the 15th Conference on Formal Grammar (FG 2010), LNCS, 7395, Copenhagen, Denmark, 2012, 66–81.Dikovsky A., “Grammars for local and long dependencies”, In Proc. of the Intern. Conf. ACL’2001, 2001, 156–163.Dikovsky A., “Grammars for local and long dependencies”, In Proc. of the Intern. Conf. ACL’2001, 2001, 156–163.Dikovsky A., “Dependencies as categories”, Proc. of Workshop Recent Advances in Dependency Grammars”. In conjunction with COLING 2004, 2004, 90–97.Dikovsky A., “Dependencies as categories”, Proc. of Workshop Recent Advances in Dependency Grammars”. In conjunction with COLING 2004, 2004, 90–97.Dikovsky A., “Proc. of the 12th Conference on Formal Grammar”, 2007, 1–12.Dikovsky A., “Proc. of the 12th Conference on Formal Grammar”, 2007, 1–12.Ginsburg S., Greibach S., “Abstract families of languages”, Mem. Amer. Math. Soc., 1969, № 87, 1–32.Ginsburg S., Greibach S., “Abstract families of languages”, Mem. Amer. Math. Soc., 1969, № 87, 1–32.Greibach S., “A new normal-form theorem for context-free phrase structure grammars”, Journal of the ACM, 12 (1965), 42–52.Greibach S., “A new normal-form theorem for context-free phrase structure grammars”, Journal of the ACM, 12 (1965), 42–52.Hack M., “Petri Net Languages”, MIT, Lab. for Computer Science, Technical Report 159, 1976.Hack M., “Petri Net Languages”, MIT, Lab. for Computer Science, Technical Report 159, 1976.Hopcroft J., Ullman J., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.Hopcroft J., Ullman J., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.Kallmeyer L., Parsing Beyond Context-Free Grammars, Cognitive Technologies, SpringerVerlag, Berlin Heidelberg, 2010.Kallmeyer L., Parsing Beyond Context-Free Grammars, Cognitive Technologies, SpringerVerlag, Berlin Heidelberg, 2010.Joshi A., Levy L., Takahashi M., “Tree adjunct grammar”, Journal of Computer and System Sciences, 1975, № 10(1), 136–163.Joshi A., Levy L., Takahashi M., “Tree adjunct grammar”, Journal of Computer and System Sciences, 1975, № 10(1), 136–163.Kanazawa M., Salvati S., “Mix is not a tree-adjoining language”, The 50th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference: Long Papers, 1, Jeju Island, Korea, 2012, 666–674.Kanazawa M., Salvati S., “Mix is not a tree-adjoining language”, The 50th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference: Long Papers, 1, Jeju Island, Korea, 2012, 666–674.Karlov B., “Abstract automata and a normal form for categorial dependency grammars”, Proc. of the 7th International Conference on Logical Aspects of Computational Linguistics (LACL 2012), LNCS, 7351, Nantes, France, 2012, 86–102.Karlov B., “Abstract automata and a normal form for categorial dependency grammars”, Proc. of the 7th International Conference on Logical Aspects of Computational Linguistics (LACL 2012), LNCS, 7351, Nantes, France, 2012, 86–102.Søgaard A., “A linear time extension of deterministic push-down automata”, Proc. of the 17th Nordic Conference of Computational Linguistics NODALIDA 2009, NEALT Proceedings Series, 4, eds. K. Jokinen, E. Bick, 2009, 182–189.Søgaard A., “A linear time extension of deterministic push-down automata”, Proc. of the 17th Nordic Conference of Computational Linguistics NODALIDA 2009, NEALT Proceedings Series, 4, eds. K. Jokinen, E. Bick, 2009, 182–189.Tesni`ere L., El´ements de syntaxe structurale. Librairie C ´ , Klincksieck, Paris, 1959.Tesni`ere L., El´ements de syntaxe structurale. Librairie C ´ , Klincksieck, Paris, 1959.Vijay-Shanker K., A Study of Tree Adjoining Grammars, Ph.D. thesis, University of Pennsylvania, 1987.Vijay-Shanker K., A Study of Tree Adjoining Grammars, Ph.D. thesis, University of Pennsylvania, 1987.Vijay-Shanker K., Weir D. J., “The equivalence of four extensions of context-free grammars”, Mathematical Systems Theory, 1994, № 27(6), 511–546.Vijay-Shanker K., Weir D. J., “The equivalence of four extensions of context-free grammars”, Mathematical Systems Theory, 1994, № 27(6), 511–546.Gladkiy A. V., Formalnye grammatiki i yazyki, Nauka, Moskva, 1973, (in Russian).Gladkiy A. V., Formalnye grammatiki i yazyki, Nauka, Moskva, 1973, (in Russian).Karlov B. N., “Normalnye formy i avtomaty dlya kategorialnykh grammatik zavisimostey”, Vestnik Tverskogo gosudarstvennogo universiteta, “Prikladnaya matematika”, 2008, 23–43, (in Russian).Karlov B. N., “Normalnye formy i avtomaty dlya kategorialnykh grammatik zavisimostey”, Vestnik Tverskogo gosudarstvennogo universiteta, “Prikladnaya matematika”, 2008, 23–43, (in Russian).

The authors declare that there are no conflicts of interest present.