(Max,+)-automata with partial observations

0491959 - MÚ 2019 RIV NL eng C - Konferenční příspěvek (zahraniční konf.)
Komenda, Jan - Lahaye, S. - Boimond, J.-L.
(Max,+)-automata with partial observations.
IFAC-PapersOnLine. Vol. 51, Issue 7. Amsterdam: Elsevier, 2018 - (De Tommasi, G.), s. 192-197. ISSN 2405-8963.
[14th Workshop on Discrete Event Systems (WODES 2018). Sorrento Coast (IT), 29.05.2018-01.06.2018]
Institucionální podpora: RVO:67985840
Klíčová slova: (Max,+)-automata * partial observations * weak bisimulation
Obor OECD: Automation and control systems
https://www.sciencedirect.com/science/article/pii/S240589631830630X?via%3Dihub

Max,+ -automata are weighted automata over the (max,+) semiring. In this paper we investigate simulation like equivalences between (max,+)-automata. Since (max,+)-automata are nondeterministic (weighted) automata, there exist extensions of bisimilarity properties that are weaker than equality of their weighted languages (formal power series). The main advantage of bisimulation like properties is that they can be checked in polynomial time, while equality (as well as inequality) of formal power series is undecidable. We show that a form of weak simulation can be used as a sufficient condition for comparing the formal power series.
Trvalý link: http://hdl.handle.net/11104/0285545