Представление многочленов мультимодальными категориальными грамматиками зависимостей
Аннотация
Категориальные грамматики зависимостей являются обобщением классических категориальных грамматик. В отличие от контекстно-свободных грамматик, они описывают структуру предложения не с помощью составляющих, а посредством синтаксических зависимостей между словами. Эти грамматики весьма выразительны и позволяют порождать многие не контекстно-свободные языки. В статье изучаются выразительные возможности одного из вариантов этих грамматик — мультимодальных категориальных грамматик зависимостей. Ранее уже было установлено, что они способны порождать неполулинейные языки. В статье исследуются возможности задания многочленов с помощью таких грамматик. Доказано, что для любого полинома существует грамматика, порождающая множество положительных значений этого полинома, записанных в унарной системе. Аналогичным образом может быть представлено и множество абсолютных величин всех ненулевых значений полинома. Установлено, что можно построить грамматики, осуществляющие вычисление значения полинома на заданном аргументе и вычисление аргумента по заданному значению полинома.
Скачивания
Литература
2. Kuhlmann M., Maletti, A. and Schiffer L. K. (2019) The Tree-Generative Capacity of Combinatory Categorial Grammars. In Proc. Foundations of Software Technology and Theoretical Computer Science. 150 of LIPIcs. Dagstuhl, Germany, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, P. 44:1–44:14.
3. Kuhlmann M., Maletti A. and Schiffer L. K. (2022) The Tree-Generative Capacity of Combinatory Categorial Grammars. Journal of Computer and System Sciences. 124. P. 214–233. DOI
4. Schiffer L. K. and Maletti A. (2021) Strong Equivalence of TAG and CCG. Transactions of the Association for Computational Linguistics. 9. P. 707–720. DOI
5. Dekhtyar M. and Dikovsky A. (2008) Generalized Categorial Dependency Grammars. Pillars of Computer Science. Lecture Notes in Computer Science. Vol 4800. Berlin, Heidelberg, Springer. P. 230–255. DOI
6. Dikovsky A. (2007) Multimodal Categorial Dependency Grammars. In Proc. of the 12th Conference on Formal Grammar (FG 2007), Dublin, Ireland. P. 1–12.
7. Béchet D. and Foret A. (2021) Incremental learning of iterated dependencies. Machine Learning. DOI
8. Dikovsky A. (2011) Categorial Dependency Grammars: from Theory to Large Scale Grammars. In Proc. of the 1st Intern. Conf. on Dependency Linguistics (Depling 2011), Barcelona, Spain. P. 262–271.
9. Foret A. and Béchet D. (2020) On Categorial Grammatical Inference and Logical Information Systems. Logic and Algorithms in Computational Linguistics 2018. Cham, Springer. P. 125–153. DOI
10. Foret A., Béchet D. and Bellynck V. (2022) Iterated Dependencies in a Breton Treebank and Implications for a Categorial Dependency Grammar. In Proc. of the 4th Celtic Language Technology Workshop within LREC2022, Marseille, France. Paris, European Language Resources Association. P. 40–46.
11. Karlov B. N. (2011) O svoistvakh yazykov, zadavaemykh mul’timodal’nymi kategorial’nymi grammatikami zavisimostei [On properties of languages generated by multimodal categorical dependency grammars]. Vestnik TvGU. Seria: Prikladnaya matematika. (22). P. 91–110. (in Russian)
12. Dekhtyar M., Dikovsky A. and Karlov B. (2012) Iterated Dependencies and Kleene Iteration. In Proc. of the 15th Conference on Formal Grammar (FG 2010), Copenhagen, Denmark. Series: LNCS. 2012. Vol. 7395. Berlin, Heidelberg, Springer, P. 66–81. DOI
13. Dekhtyar M., Karlov B. and Dikovsky A. (2015) Categorial Dependency Grammars. Theoretical Computer Science. 579. P. 33–63. DOI
14. Ginsburg S. (1966) The Mathematical Theory of Context-Free Languages. New York, McGraw-Hill, Inc. 232 p.
15. Joshi A. K. and Schabes Y. (1997) Tree-Adjoining Grammars. Handbook of Formal Languages. Berlin, Heidelberg, Springer. P. 69–123. DOI
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
