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

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों:	Indzhev, E, Kiefer, S
स्वरूप:	Journal article
भाषा:	English
प्रकाशित:	Elsevier 2022

समान संसाधन

Markov chains and unambiguous automata
द्वारा: Baier, C, और अन्य
प्रकाशित: (2023)

Markov chains and unambiguous Büchi automata
द्वारा: Baier, C, और अन्य
प्रकाशित: (2016)

Markov Chains and Unambiguous Büchi Automata
द्वारा: Kiefer, S, और अन्य
प्रकाशित: (2016)

Lower bounds for unambiguous automata via communication complexity
द्वारा: Göös, M, और अन्य
प्रकाशित: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
द्वारा: Kiefer, S, और अन्य
प्रकाशित: (2019)

Unambiguous and finitely ambiguous automata
द्वारा: Widdershoven, C
प्रकाशित: (2022)

Cliques and Clique Covers in Interval-Valued Fuzzy Graphs
द्वारा: Napur Patra, और अन्य
प्रकाशित: (2021-06-01)

On clique convergence of graphs
द्वारा: S.M. Hegde, और अन्य
प्रकाशित: (2016-12-01)

Probabilistic Cellular Automata Monte Carlo for the Maximum Clique Problem
द्वारा: Alessio Troiani
प्रकाशित: (2024-09-01)

on the number of cliques and cycles in graphs
द्वारा: Mojgan Emami, और अन्य
प्रकाशित: (2013-06-01)

Inverse Clique Domination in Graphs
द्वारा: Carmelita Loquias, और अन्य
प्रकाशित: (2016-12-01)

Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
द्वारा: Chuan-Min Lee
प्रकाशित: (2021-01-01)

Clique covers of H-free graphs
द्वारा: Nguyen, T, और अन्य
प्रकाशित: (2023)

Learning graph representations with maximal cliques
द्वारा: Molaei, S, और अन्य
प्रकाशित: (2021)

Edge-regular graphs with regular cliques
द्वारा: Greaves, Gary Royden Watson, और अन्य
प्रकाशित: (2019)

Cliques of Graph Convolutional Networks for Recommendation
द्वारा: Zhenye Pan, और अन्य
प्रकाशित: (2024-01-01)

Complexity results on graphs with few cliques
द्वारा: Bill Rosgen, और अन्य
प्रकाशित: (2007-01-01)

Largest cliques in connected supermagic graphs
द्वारा: Anna Lladó
प्रकाशित: (2005-01-01)

Cliques Are Bricks for k-CT Graphs
द्वारा: Václav Snášel, और अन्य
प्रकाशित: (2021-05-01)

Graph Planarity by Replacing Cliques with Paths
द्वारा: Patrizio Angelini, और अन्य
प्रकाशित: (2020-08-01)

Complexity Results on Graphs with Few Cliques
द्वारा: Bill Rosgen, और अन्य
प्रकाशित: (2007-01-01)

Clique colouring of binomial random graphs
द्वारा: McDiarmid, C, और अन्य
प्रकाशित: (2018)

A result on interated clique graphs /
द्वारा: 295030 Lim, Chong-Keong
प्रकाशित: (1978)

On the clique number of a strongly regular graph
द्वारा: Greaves, Gary Royden Watson, और अन्य
प्रकाशित: (2021)

Exploratory Data Analysis and Searching Cliques in Graphs
द्वारा: András Hubai, और अन्य
प्रकाशित: (2024-03-01)

Independent sets in graphs with an excluded clique minor
द्वारा: David R. Wood
प्रकाशित: (2007-01-01)

Clique cycle transversals in graphs with few P₄'s
द्वारा: Raquel Bravo, और अन्य
प्रकाशित: (2013-09-01)

On graphs with equal coprime index and clique number
द्वारा: Chetan Patil, और अन्य
प्रकाशित: (2023-09-01)

The DP Color Function of Clique-Gluings of Graphs
द्वारा: Hemanshu Kaul, और अन्य
प्रकाशित: (2023-09-01)

Independent Sets in Graphs with an Excluded Clique Minor
द्वारा: David R. Wood
प्रकाशित: (2007-01-01)

The clique number and some Hamiltonian properties of graphs
द्वारा: Rao Li
प्रकाशित: (2021-08-01)

On probe 2-clique graphs and probe diamond-free graphs
द्वारा: Flavia Bonomo, और अन्य
प्रकाशित: (2015-03-01)

Number of Cliques in Graphs with a Forbidden Subdivision
द्वारा: Lee, Choongbum, और अन्य
प्रकाशित: (2016)

Bounds on the Clique and the Independence Number for Certain Classes of Graphs
द्वारा: Valentin E. Brimkov, और अन्य
प्रकाशित: (2024-01-01)

GraphZIP: a clique-based sparse graph compression method
द्वारा: Ryan A. Rossi, और अन्य
प्रकाशित: (2018-03-01)

Another construction of edge-regular graphs with regular cliques
द्वारा: Greaves, Gary Royden Watson, और अन्य
प्रकाशित: (2020)

A Note on the Signed Clique Domination Numbers of Graphs
द्वारा: Baogen Xu, और अन्य
प्रकाशित: (2022-01-01)

Comments on the Clique Number of Zero-Divisor Graphs of Zn
द्वारा: Yanzhao Tian, और अन्य
प्रकाशित: (2022-01-01)

Graphs with Strong Proper Connection Numbers and Large Cliques
द्वारा: Yingbin Ma, और अन्य
प्रकाशित: (2023-04-01)

A Spectral Characterization of the S-Clique Extension of the Triangular Graphs
द्वारा: Tan Ying-Ying, और अन्य
प्रकाशित: (2020-05-01)