Jump Complexity of Deterministic Finite Automata with Translucent Letters
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916806429507584 |
|---|---|
| author | Fazekas, Szilárd Zsolt Mitrana, Victor Păun, Andrei Păun, Mihaela |
| author_facet | Fazekas, Szilárd Zsolt Mitrana, Victor Păun, Andrei Păun, Mihaela |
| contents | We investigate a dynamical complexity measure defined for finite automata with translucent letters (FAwtl). Roughly, this measure counts the minimal number of necessary jumps for such an automaton in order to accept an input. The model considered here is the deterministic finite automaton with translucent letters (DFAwtl). Unlike in the case of the nondeterministic variant, the function describing the jump complexity of any DFAwtl is either bounded by a constant or it is linear. We give a polynomial-time algorithm for deciding whether the jump complexity of a DFAwtl is constant-bounded or linear and we prove that the equivalence problem for DFAwtl of $\bigo(1)$ jump complexity is decidable. We also consider another fundamental problem for extensions of finite automata models, deciding whether the language accepted by a FAwtl is regular. We give a positive partial answer for DFAwtl over the binary alphabet, in contrast with the case of NFAwtl, where the problem is undecidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18393 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Jump Complexity of Deterministic Finite Automata with Translucent Letters Fazekas, Szilárd Zsolt Mitrana, Victor Păun, Andrei Păun, Mihaela Formal Languages and Automata Theory 68Q45 F.4.3; F.2.2 We investigate a dynamical complexity measure defined for finite automata with translucent letters (FAwtl). Roughly, this measure counts the minimal number of necessary jumps for such an automaton in order to accept an input. The model considered here is the deterministic finite automaton with translucent letters (DFAwtl). Unlike in the case of the nondeterministic variant, the function describing the jump complexity of any DFAwtl is either bounded by a constant or it is linear. We give a polynomial-time algorithm for deciding whether the jump complexity of a DFAwtl is constant-bounded or linear and we prove that the equivalence problem for DFAwtl of $\bigo(1)$ jump complexity is decidable. We also consider another fundamental problem for extensions of finite automata models, deciding whether the language accepted by a FAwtl is regular. We give a positive partial answer for DFAwtl over the binary alphabet, in contrast with the case of NFAwtl, where the problem is undecidable. |
| title | Jump Complexity of Deterministic Finite Automata with Translucent Letters |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3; F.2.2 |
| url | https://arxiv.org/abs/2506.18393 |