On A. V. Anisimov's problem for finding a polynomial algorithm checking inclusion of context-free languages in group languages
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908844017319936 |
|---|---|
| author | Yordzhev, Krasimir |
| author_facet | Yordzhev, Krasimir |
| contents | The work investigates the problem of whether a context-free language is a subset of a group language. A.~V. Anisimov has shown that the problem of determining the unambiguity of finite automata is a special case of this problem. Then the question of finding polynomial algorithm verifying the inclusion of context-free languages in group languages naturally arises. The article focuses on this open problem. For the purpose, the paper describes an unconventional method of description of context-free languages, namely a representation with the help of a finite digraph whose arcs are labelled with a specially defined monoid $\mathcal{U}$. Also, we define a semiring $\mathcal{S}_\mathcal{U}$ whose elements are the set $2^\mathcal{U}$ of all subsets of $\mathcal{U}$ and with operations - product and union of the elements of $2^\mathcal{U}$. The described algorithm executes no more than $O(n^3)$ operations in $\mathcal{S}_\mathcal{U}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18305 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On A. V. Anisimov's problem for finding a polynomial algorithm checking inclusion of context-free languages in group languages Yordzhev, Krasimir Formal Languages and Automata Theory Combinatorics 68Q45, 68Q70 The work investigates the problem of whether a context-free language is a subset of a group language. A.~V. Anisimov has shown that the problem of determining the unambiguity of finite automata is a special case of this problem. Then the question of finding polynomial algorithm verifying the inclusion of context-free languages in group languages naturally arises. The article focuses on this open problem. For the purpose, the paper describes an unconventional method of description of context-free languages, namely a representation with the help of a finite digraph whose arcs are labelled with a specially defined monoid $\mathcal{U}$. Also, we define a semiring $\mathcal{S}_\mathcal{U}$ whose elements are the set $2^\mathcal{U}$ of all subsets of $\mathcal{U}$ and with operations - product and union of the elements of $2^\mathcal{U}$. The described algorithm executes no more than $O(n^3)$ operations in $\mathcal{S}_\mathcal{U}$. |
| title | On A. V. Anisimov's problem for finding a polynomial algorithm checking inclusion of context-free languages in group languages |
| topic | Formal Languages and Automata Theory Combinatorics 68Q45, 68Q70 |
| url | https://arxiv.org/abs/2602.18305 |