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...
| Hlavní autoři: | , |
|---|---|
| Médium: | Journal article |
| Jazyk: | English |
| Vydáno: |
Elsevier
2022
|
| _version_ | 1826307660937428992 |
|---|---|
| author | Indzhev, E Kiefer, S |
| author_facet | Indzhev, E Kiefer, S |
| author_sort | Indzhev, E |
| collection | OXFORD |
| description | 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 an analysis of a problem from extremal graph theory: we show that for any graph with n vertices, the product of the number of its cliques with the number of its cocliques (independent sets) is bounded by (n + 1)2n. |
| first_indexed | 2024-03-07T07:08:04Z |
| format | Journal article |
| id | oxford-uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:08:04Z |
| publishDate | 2022 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf542022-05-17T09:50:14ZOn complementing unambiguous automata and graphs with many cliques and cocliquesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54EnglishSymplectic ElementsElsevier2022Indzhev, EKiefer, SWe 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 an analysis of a problem from extremal graph theory: we show that for any graph with n vertices, the product of the number of its cliques with the number of its cocliques (independent sets) is bounded by (n + 1)2n. |
| spellingShingle | Indzhev, E Kiefer, S On complementing unambiguous automata and graphs with many cliques and cocliques |
| title | On complementing unambiguous automata and graphs with many cliques and cocliques |
| title_full | On complementing unambiguous automata and graphs with many cliques and cocliques |
| title_fullStr | On complementing unambiguous automata and graphs with many cliques and cocliques |
| title_full_unstemmed | On complementing unambiguous automata and graphs with many cliques and cocliques |
| title_short | On complementing unambiguous automata and graphs with many cliques and cocliques |
| title_sort | on complementing unambiguous automata and graphs with many cliques and cocliques |
| work_keys_str_mv | AT indzheve oncomplementingunambiguousautomataandgraphswithmanycliquesandcocliques AT kiefers oncomplementingunambiguousautomataandgraphswithmanycliquesandcocliques |