Weighted automata and multi-valued logics over arbitrary bounded lattices (Q764336): Difference between revisions

The paper gives general lattice-valued versions of the fundamental results of Kleene and Büchi-Elgot-Trakhtenbrot, which show that the languages recognized by automata are exactly the rational languages and, equivalently, the languages definable in monadic second-order logic. The authors consider the general setting of bi-locally finite strong bimonoids. A bimonoid is a structure \((A,+,\cdot,0,1)\) such that \((A,+,0)\) and \((A,\cdot,1)\) are monoids. A bimonoid is said to be strong if the operation \(+\) is commutative and \(a\cdot 0=0=0\cdot a\) for every \(a\in A\). A strong bimonoid is bi-locally finite if for every finite \(B\subseteq A\), the smallest submonoid of \((A,+,0)\) and the smallest submonoid of \((A,\cdot,1)\) containing \(B\) are finite. A strong bimonoid in which multiplication distributes over addition is a semiring. Since not all strong bimonoids are semirings, the results of this paper non-trivially generalized the corresponding results in the theory of semiring-weighted automata [\textit{S. Eilenberg}, Automata, languages, and machines. Vol. A. New York-London: Academic Press (1974; Zbl 0317.94045); \textit{A. Salomaa} and \textit{M. Soittola}, Automata-theoretic aspects of formal power series. New York-Heidelberg-Berlin: Springer-Verlag (1978; Zbl 0377.68039); \textit{W. Kuich} and \textit{A. Salomaa}, Semirings, automata, languages. Berlin etc.: Springer-Verlag (1986; Zbl 0582.68002); \textit{J. Berstel} and \textit{Ch. Reutenauer}, Rational series and their languages. Berlin etc.: Springer-Verlag (1988; Zbl 0668.68005); \textit{W. Kuich}, ``Semirings and formal power series: their relevance to formal languages and automata'', in: Handbook of formal languages. Vol. 1. Berlin: Springer. 609--677 (1997; Zbl 0866.68057); \textit{M. Droste} (ed.), \textit{W. Kuich} (ed.) and \textit{H. Vogler} (ed.), Handbook of weighted automata. Berlin: Springer (2009; Zbl 1200.68001)].