A Myhill-Nerode Type Characterization of 2detLIN Languages
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913950431444992 |
|---|---|
| author | Nagy, Benedek |
| author_facet | Nagy, Benedek |
| contents | Linear automata are automata with two reading heads starting from the two extremes of the input, are equivalent to 5' -> 3' Watson-Crick (WK) finite automata. The heads read the input in opposite directions and the computation finishes when the heads meet. These automata accept the class LIN of linear languages. The deterministic counterpart of these models, on the one hand, is less expressive, as only a proper subset of LIN, the class 2detLIN is accepted; and on the other hand, they are also equivalent in the sense of the class of the accepted languages. Now, based on these automata models, we characterize the class of 2detLIN languages with a Myhill-Nerode type of equivalence classes. However, as these automata may do the computation of both the prefix and the suffix of the input, we use prefix-suffix pairs in our classes. Additionally, it is proven that finitely many classes in the characterization match with the 2detLIN languages, but we have some constraints on the used prefix-suffix pairs, i.e., the characterization should have the property to be complete and it must not have any crossing pairs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15316 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Myhill-Nerode Type Characterization of 2detLIN Languages Nagy, Benedek Formal Languages and Automata Theory Discrete Mathematics Data Structures and Algorithms F.1.1;F.4.3;F.1.3 Linear automata are automata with two reading heads starting from the two extremes of the input, are equivalent to 5' -> 3' Watson-Crick (WK) finite automata. The heads read the input in opposite directions and the computation finishes when the heads meet. These automata accept the class LIN of linear languages. The deterministic counterpart of these models, on the one hand, is less expressive, as only a proper subset of LIN, the class 2detLIN is accepted; and on the other hand, they are also equivalent in the sense of the class of the accepted languages. Now, based on these automata models, we characterize the class of 2detLIN languages with a Myhill-Nerode type of equivalence classes. However, as these automata may do the computation of both the prefix and the suffix of the input, we use prefix-suffix pairs in our classes. Additionally, it is proven that finitely many classes in the characterization match with the 2detLIN languages, but we have some constraints on the used prefix-suffix pairs, i.e., the characterization should have the property to be complete and it must not have any crossing pairs. |
| title | A Myhill-Nerode Type Characterization of 2detLIN Languages |
| topic | Formal Languages and Automata Theory Discrete Mathematics Data Structures and Algorithms F.1.1;F.4.3;F.1.3 |
| url | https://arxiv.org/abs/2507.15316 |