Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.13376 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916270471905280 |
|---|---|
| author | Gill, Kenneth |
| author_facet | Gill, Kenneth |
| contents | We introduce a new complexity measure for finite strings using probabilistic finite-state automata (PFAs), in the same spirit as existing notions employing DFAs and NFAs, and explore its properties. The PFA complexity $A_P(x)$ is the least number of states of a PFA for which $x$ is the most likely string of its length to be accepted. The variant $A_{P,δ}(x)$ adds a real-valued parameter $δ$ specifying a required lower bound on the gap in acceptance probabilities between $x$ and other strings. We prove $A_{P,δ}$ is $δ$-computable for all $δ$, relate $A_P$ to the DFA and NFA complexities, and obtain a complete classification of binary strings with $A_P=2$. Finally, we discuss several other variations on $A_P$ with a view to obtaining additional desirable properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13376 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Probabilistic automatic complexity of finite strings Gill, Kenneth Formal Languages and Automata Theory Logic 68Q30 We introduce a new complexity measure for finite strings using probabilistic finite-state automata (PFAs), in the same spirit as existing notions employing DFAs and NFAs, and explore its properties. The PFA complexity $A_P(x)$ is the least number of states of a PFA for which $x$ is the most likely string of its length to be accepted. The variant $A_{P,δ}(x)$ adds a real-valued parameter $δ$ specifying a required lower bound on the gap in acceptance probabilities between $x$ and other strings. We prove $A_{P,δ}$ is $δ$-computable for all $δ$, relate $A_P$ to the DFA and NFA complexities, and obtain a complete classification of binary strings with $A_P=2$. Finally, we discuss several other variations on $A_P$ with a view to obtaining additional desirable properties. |
| title | Probabilistic automatic complexity of finite strings |
| topic | Formal Languages and Automata Theory Logic 68Q30 |
| url | https://arxiv.org/abs/2402.13376 |