Weighted automata and multi-valued logics over arbitrary bounded lattices (Q764336): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:46, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Weighted automata and multi-valued logics over arbitrary bounded lattices |
scientific article |
Statements
Weighted automata and multi-valued logics over arbitrary bounded lattices (English)
0 references
13 March 2012
0 references
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)].
0 references
weighted automata
0 references
semiring
0 references
formal power series
0 references
monadic second-order logic
0 references
lattice-valued logic
0 references