1 citations · 2 across the 7 of their papers we have counts for
7 papers
Completely Reachable Road Coloring
Mikhail V. Volkov, Yinfeng Zhu
We characterize the digraphs that admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable automaton. This class o…
Adversarial Synchronization
Anton E. Lipin, Mikhail V. Volkov
We study a variant of the synchronization game on finite deterministic automata. In this game, Alice chooses one input letter of an automaton on each of her moves while Bob may…
A new Boolean matrix representation for Catalan semirings
Mikhail Volkov
We construct a faithful representation of the semiring of all order-preserving decreasing transformations of a chain with elements by Boolean upper triangular -mat…
List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
Mikhail V. Volkov
We survey results in the literature that establish the Černý conjecture for various classes of finite automata. We also list classes for which the conjecture remains open, but a qu…
Embedding lattices of quasivarieties of periodic groups into lattices of additively idempotent semiring varieties: An algebraic proof
Miaomiao Ren, Xianzhong Zhao, Mikhail V. Volkov
A general result by Jackson (Flat algebras and the translation of universal Horn logic to equational logic, J. Symb. Log. 73(1) (2008) 90--128) implies that the lattice of all quas…
Identities of triangular Boolean matrices
Mikhail V. Volkov
We give a combinatorial characterization of the identities holding in the semiring of all upper triangular Boolean -matrices and apply the characterization to computatio…
Don's conjecture for binary completely reachable automata: an approach and its limitations
David Casas, Mikhail V. Volkov
A deterministic finite automaton in which every non-empty set of states occurs as the image of the whole state set under the action of a suitable input word is called completely re…