On complementing unambiguous automata and graphs with many cliques and cocliques
We show that for any unambiguous finite automaton with n states there exists an unambiguous finite automaton with √n + 1 · 2n/2 states that recognizes the complement language. This builds and improves upon a similar result by Jirásek et al. (2018) [1]. Our improvement is based on a reduction to and...
| Հիմնական հեղինակներ: | , |
|---|---|
| Ձևաչափ: | Journal article |
| Լեզու: | English |
| Հրապարակվել է: |
Elsevier
2022
|