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

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Indzhev, E, Kiefer, S
Formáid:	Journal article
Teanga:	English
Foilsithe / Cruthaithe:	Elsevier 2022

Míreanna comhchosúla

Markov chains and unambiguous automata
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2023)

Markov chains and unambiguous Büchi automata
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2016)

Markov Chains and Unambiguous Büchi Automata
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2016)

Lower bounds for unambiguous automata via communication complexity
de réir: Göös, M, et al.
Foilsithe / Cruthaithe: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2019)

Unambiguous and finitely ambiguous automata
de réir: Widdershoven, C
Foilsithe / Cruthaithe: (2022)

Cliques and Clique Covers in Interval-Valued Fuzzy Graphs
de réir: Napur Patra, et al.
Foilsithe / Cruthaithe: (2021-06-01)

On clique convergence of graphs
de réir: S.M. Hegde, et al.
Foilsithe / Cruthaithe: (2016-12-01)

Probabilistic Cellular Automata Monte Carlo for the Maximum Clique Problem
de réir: Alessio Troiani
Foilsithe / Cruthaithe: (2024-09-01)

on the number of cliques and cycles in graphs
de réir: Mojgan Emami, et al.
Foilsithe / Cruthaithe: (2013-06-01)

Inverse Clique Domination in Graphs
de réir: Carmelita Loquias, et al.
Foilsithe / Cruthaithe: (2016-12-01)

Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
de réir: Chuan-Min Lee
Foilsithe / Cruthaithe: (2021-01-01)

Clique covers of H-free graphs
de réir: Nguyen, T, et al.
Foilsithe / Cruthaithe: (2023)

Learning graph representations with maximal cliques
de réir: Molaei, S, et al.
Foilsithe / Cruthaithe: (2021)

Edge-regular graphs with regular cliques
de réir: Greaves, Gary Royden Watson, et al.
Foilsithe / Cruthaithe: (2019)

Cliques of Graph Convolutional Networks for Recommendation
de réir: Zhenye Pan, et al.
Foilsithe / Cruthaithe: (2024-01-01)

Complexity results on graphs with few cliques
de réir: Bill Rosgen, et al.
Foilsithe / Cruthaithe: (2007-01-01)

Largest cliques in connected supermagic graphs
de réir: Anna Lladó
Foilsithe / Cruthaithe: (2005-01-01)

Cliques Are Bricks for k-CT Graphs
de réir: Václav Snášel, et al.
Foilsithe / Cruthaithe: (2021-05-01)

Graph Planarity by Replacing Cliques with Paths
de réir: Patrizio Angelini, et al.
Foilsithe / Cruthaithe: (2020-08-01)

Complexity Results on Graphs with Few Cliques
de réir: Bill Rosgen, et al.
Foilsithe / Cruthaithe: (2007-01-01)

Clique colouring of binomial random graphs
de réir: McDiarmid, C, et al.
Foilsithe / Cruthaithe: (2018)

A result on interated clique graphs /
de réir: 295030 Lim, Chong-Keong
Foilsithe / Cruthaithe: (1978)

On the clique number of a strongly regular graph
de réir: Greaves, Gary Royden Watson, et al.
Foilsithe / Cruthaithe: (2021)

Exploratory Data Analysis and Searching Cliques in Graphs
de réir: András Hubai, et al.
Foilsithe / Cruthaithe: (2024-03-01)

Independent sets in graphs with an excluded clique minor
de réir: David R. Wood
Foilsithe / Cruthaithe: (2007-01-01)

Clique cycle transversals in graphs with few P₄'s
de réir: Raquel Bravo, et al.
Foilsithe / Cruthaithe: (2013-09-01)

On graphs with equal coprime index and clique number
de réir: Chetan Patil, et al.
Foilsithe / Cruthaithe: (2023-09-01)

The DP Color Function of Clique-Gluings of Graphs
de réir: Hemanshu Kaul, et al.
Foilsithe / Cruthaithe: (2023-09-01)

Independent Sets in Graphs with an Excluded Clique Minor
de réir: David R. Wood
Foilsithe / Cruthaithe: (2007-01-01)

The clique number and some Hamiltonian properties of graphs
de réir: Rao Li
Foilsithe / Cruthaithe: (2021-08-01)

On probe 2-clique graphs and probe diamond-free graphs
de réir: Flavia Bonomo, et al.
Foilsithe / Cruthaithe: (2015-03-01)

Number of Cliques in Graphs with a Forbidden Subdivision
de réir: Lee, Choongbum, et al.
Foilsithe / Cruthaithe: (2016)

Bounds on the Clique and the Independence Number for Certain Classes of Graphs
de réir: Valentin E. Brimkov, et al.
Foilsithe / Cruthaithe: (2024-01-01)

GraphZIP: a clique-based sparse graph compression method
de réir: Ryan A. Rossi, et al.
Foilsithe / Cruthaithe: (2018-03-01)

Another construction of edge-regular graphs with regular cliques
de réir: Greaves, Gary Royden Watson, et al.
Foilsithe / Cruthaithe: (2020)

A Note on the Signed Clique Domination Numbers of Graphs
de réir: Baogen Xu, et al.
Foilsithe / Cruthaithe: (2022-01-01)

Comments on the Clique Number of Zero-Divisor Graphs of Zn
de réir: Yanzhao Tian, et al.
Foilsithe / Cruthaithe: (2022-01-01)

Graphs with Strong Proper Connection Numbers and Large Cliques
de réir: Yingbin Ma, et al.
Foilsithe / Cruthaithe: (2023-04-01)

A Spectral Characterization of the S-Clique Extension of the Triangular Graphs
de réir: Tan Ying-Ying, et al.
Foilsithe / Cruthaithe: (2020-05-01)