From the 1 of 6 linked papers with an AI index.
6 papers
Completely Reachable Road Coloring
Mikhail V. Volkov, Yinfeng Zhu
The paper characterizes directed graphs that can be edge‑labeled by a finite alphabet to produce a completely reachable automaton, provides a polynomial‑time recognition algorithm,…
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…
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…
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…