Li, Yong 
ORCID: 0000-0002-7301-9234, Schewe, Sven ORCID: 0000-0002-9093-9518 and Tang, Qiyi ORCID: 0000-0002-9265-3011
(2023)
A novel family of finite automata for recognizing and learning
$ω$-regular languages.
[Preprint]
|
PDF
LimitFDFA.pdf - Other Download (536kB) | Preview |
Abstract
Families of DFAs (FDFAs) have recently been introduced as a new representation of $\omega$-regular languages. They target ultimately periodic words, with acceptors revolving around accepting some representation $u\cdot v^\omega$. Three canonical FDFAs have been suggested, called periodic, syntactic, and recurrent. We propose a fourth one, limit FDFAs, which can be exponentially coarser than periodic FDFAs and are more succinct than syntactic FDFAs, while they are incomparable (and dual to) recurrent FDFAs. We show that limit FDFAs can be easily used to check not only whether {\omega}-languages are regular, but also whether they are accepted by deterministic B\"uchi automata. We also show that canonical forms can be left behind in applications: the limit and recurrent FDFAs can complement each other nicely, and it may be a good way forward to use a combination of both. Using this observation as a starting point, we explore making more efficient use of Myhill-Nerode's right congruences in aggressively increasing the number of don't-care cases in order to obtain smaller progress automata. In pursuit of this goal, we gain succinctness, but pay a high price by losing constructiveness.
| Item Type: | Preprint |
|---|---|
| Additional Information: | 30 pages, accepted at ATVA 2023 |
| Uncontrolled Keywords: | cs.FL, cs.FL |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 20 Jul 2023 10:27 |
| Last Modified: | 15 Mar 2024 18:51 |
| DOI: | 10.48550/arxiv.2307.07490 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3171807 |
Dimensions
Dimensions
