Advertisement
Published in:
2010 | OriginalPaper | Chapter
Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices
Authors : Manfred Droste, Heiko Vogler
Published in: Developments in Language Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We show that
${\mathcal L}$
-weighted automata,
${\mathcal L}$
-rational series, and
$\mathcal L$
-valued monadic second-order logic have the same expressive power, for any bounded lattice
$\mathcal L$
and for finite and infinite words. This extends classical results of Kleene and Büchi to arbitrary bounded lattices, without any distributivity assumption that is fundamental in the theory of weighted automata over semirings. In fact, we obtain these results for large classes of strong bimonoids which properly contain all bounded lattices.