On complementing unambiguous automata and graphs with many cliques and cocliques

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

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Indzhev, E, Kiefer, S
Format:	Journal article
Sprog:	English
Udgivet:	Elsevier 2022

Lignende værker

Markov chains and unambiguous automata
af: Baier, C, et al.
Udgivet: (2023)

Markov chains and unambiguous Büchi automata
af: Baier, C, et al.
Udgivet: (2016)

Markov Chains and Unambiguous Büchi Automata
af: Kiefer, S, et al.
Udgivet: (2016)

Lower bounds for unambiguous automata via communication complexity
af: Göös, M, et al.
Udgivet: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
af: Kiefer, S, et al.
Udgivet: (2019)

Unambiguous and finitely ambiguous automata
af: Widdershoven, C
Udgivet: (2022)

Cliques and Clique Covers in Interval-Valued Fuzzy Graphs
af: Napur Patra, et al.
Udgivet: (2021-06-01)

On clique convergence of graphs
af: S.M. Hegde, et al.
Udgivet: (2016-12-01)

Probabilistic Cellular Automata Monte Carlo for the Maximum Clique Problem
af: Alessio Troiani
Udgivet: (2024-09-01)

on the number of cliques and cycles in graphs
af: Mojgan Emami, et al.
Udgivet: (2013-06-01)

Inverse Clique Domination in Graphs
af: Carmelita Loquias, et al.
Udgivet: (2016-12-01)

Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
af: Chuan-Min Lee
Udgivet: (2021-01-01)

Clique covers of H-free graphs
af: Nguyen, T, et al.
Udgivet: (2023)

Learning graph representations with maximal cliques
af: Molaei, S, et al.
Udgivet: (2021)

Edge-regular graphs with regular cliques
af: Greaves, Gary Royden Watson, et al.
Udgivet: (2019)

Cliques of Graph Convolutional Networks for Recommendation
af: Zhenye Pan, et al.
Udgivet: (2024-01-01)

Complexity results on graphs with few cliques
af: Bill Rosgen, et al.
Udgivet: (2007-01-01)

Largest cliques in connected supermagic graphs
af: Anna Lladó
Udgivet: (2005-01-01)

Cliques Are Bricks for k-CT Graphs
af: Václav Snášel, et al.
Udgivet: (2021-05-01)

Graph Planarity by Replacing Cliques with Paths
af: Patrizio Angelini, et al.
Udgivet: (2020-08-01)

Complexity Results on Graphs with Few Cliques
af: Bill Rosgen, et al.
Udgivet: (2007-01-01)

Clique colouring of binomial random graphs
af: McDiarmid, C, et al.
Udgivet: (2018)

A result on interated clique graphs /
af: 295030 Lim, Chong-Keong
Udgivet: (1978)

On the clique number of a strongly regular graph
af: Greaves, Gary Royden Watson, et al.
Udgivet: (2021)

Exploratory Data Analysis and Searching Cliques in Graphs
af: András Hubai, et al.
Udgivet: (2024-03-01)

Independent sets in graphs with an excluded clique minor
af: David R. Wood
Udgivet: (2007-01-01)

Clique cycle transversals in graphs with few P₄'s
af: Raquel Bravo, et al.
Udgivet: (2013-09-01)

On graphs with equal coprime index and clique number
af: Chetan Patil, et al.
Udgivet: (2023-09-01)

The DP Color Function of Clique-Gluings of Graphs
af: Hemanshu Kaul, et al.
Udgivet: (2023-09-01)

Independent Sets in Graphs with an Excluded Clique Minor
af: David R. Wood
Udgivet: (2007-01-01)

The clique number and some Hamiltonian properties of graphs
af: Rao Li
Udgivet: (2021-08-01)

On probe 2-clique graphs and probe diamond-free graphs
af: Flavia Bonomo, et al.
Udgivet: (2015-03-01)

Number of Cliques in Graphs with a Forbidden Subdivision
af: Lee, Choongbum, et al.
Udgivet: (2016)

Bounds on the Clique and the Independence Number for Certain Classes of Graphs
af: Valentin E. Brimkov, et al.
Udgivet: (2024-01-01)

GraphZIP: a clique-based sparse graph compression method
af: Ryan A. Rossi, et al.
Udgivet: (2018-03-01)

Another construction of edge-regular graphs with regular cliques
af: Greaves, Gary Royden Watson, et al.
Udgivet: (2020)

A Note on the Signed Clique Domination Numbers of Graphs
af: Baogen Xu, et al.
Udgivet: (2022-01-01)

Comments on the Clique Number of Zero-Divisor Graphs of Zn
af: Yanzhao Tian, et al.
Udgivet: (2022-01-01)

Graphs with Strong Proper Connection Numbers and Large Cliques
af: Yingbin Ma, et al.
Udgivet: (2023-04-01)

A Spectral Characterization of the S-Clique Extension of the Triangular Graphs
af: Tan Ying-Ying, et al.
Udgivet: (2020-05-01)