PDA with Independent Counters
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. T...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2015-04-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/239 |
| _version_ | 1797877898063904768 |
|---|---|
| author | Michael Dekhtyar Boris Karlov |
| author_facet | Michael Dekhtyar Boris Karlov |
| author_sort | Michael Dekhtyar |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T02:25:17Z |
| format | Article |
| id | doaj.art-ba9d9ef03c7a440aa501c34f526f828d |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:17Z |
| publishDate | 2015-04-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-ba9d9ef03c7a440aa501c34f526f828d2023-03-13T08:07:33ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172015-04-0122217619610.18255/1818-1015-2015-2-176-196232PDA with Independent CountersMichael Dekhtyar0Boris Karlov1Тверской государственный университетТверской государственный университет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.https://www.mais-journal.ru/jour/article/view/239автоматыформальные грамматики и языкимагазинные автоматы с независимыми счётчикамипроективная и непроективная зависимостькатегориальная грамматика зависимостеймультимодальная категориальная грамматика зависимостеймагазинные автоматы со стеками |
| spellingShingle | Michael Dekhtyar Boris Karlov PDA with Independent Counters Моделирование и анализ информационных систем автоматы формальные грамматики и языки магазинные автоматы с независимыми счётчиками проективная и непроективная зависимость категориальная грамматика зависимостей мультимодальная категориальная грамматика зависимостей магазинные автоматы со стеками |
| title | PDA with Independent Counters |
| title_full | PDA with Independent Counters |
| title_fullStr | PDA with Independent Counters |
| title_full_unstemmed | PDA with Independent Counters |
| title_short | PDA with Independent Counters |
| title_sort | pda with independent counters |
| topic | автоматы формальные грамматики и языки магазинные автоматы с независимыми счётчиками проективная и непроективная зависимость категориальная грамматика зависимостей мультимодальная категориальная грамматика зависимостей магазинные автоматы со стеками |
| url | https://www.mais-journal.ru/jour/article/view/239 |
| work_keys_str_mv | AT michaeldekhtyar pdawithindependentcounters AT boriskarlov pdawithindependentcounters |