Movatterモバイル変換

No categories

Direct download   Export citation   Bookmark   3 citations  

Recently, two apparently quite different duality-based approaches to automata minimisation have appeared. One is based on ideas that originated from the controllability-observability duality from systems theory, and the other is based on ideas derived from Stone-type dualities specifically linking coalgebras with algebraic structures derived from modal logics. In the present paper, we develop a more abstract view and unify the two approaches. We show that dualities, or more generally dual adjunctions, between categories can be lifted to dual adjunctions between categories (...) of coalgebras and algebras, and from there to automata with initial as well as final states. As in the Stone-duality approach, algebras are essentially logics for reasoning about the automata. By exploiting the ability to pass between these categories, we show that one can minimize the corresponding automata. We give an abstract minimisation algorithm that has several instances, including the celebrated Brzozowski minimisation algorithm. We further develop three examples that have been treated in previous works: deterministic Kripke frames based on a Stone-type duality, weighted automata based on the self-duality of semimodules, and topological automata based on Gelfand duality. As a new example, we develop alternating automata based on the discrete duality between sets and complete atomic Boolean algebras. (shrink)

No categories

Direct download   Export citation   Bookmark  

No categories

Direct download   Export citation   Bookmark  

No categories

Direct download   Export citation   Bookmark   1 citation