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 an an...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2022-08, Vol.177, p.106270, Article 106270
Main Authors: Indzhev, Emil, Kiefer, Stefan
Format: Article
Language:English
Subjects:
Formal languages
Graphs
State complexity
Unambiguous automata
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. •We give a bound on the state complexity of complementing unambiguous automata.•Our proof is based on a reduction to a problem from extremal graph theory.•Loosely speaking, we show that any graph has few cliques or few cocliques.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2022.106270