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)