Coalgebraic trace semantics via forgetful logics
We use modal logic as a framework for coalgebraic trace semantics, and show the flexibility of the approach with concrete examples such as the language semantics of weighted, alternating and tree automata, and the trace semantics of generative probabilistic systems. We provide a sufficient condition...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2017-04-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2622/pdf |
| _version_ | 1827322863231696896 |
|---|---|
| author | Bartek Klin Jurriaan Rot |
| author_facet | Bartek Klin Jurriaan Rot |
| author_sort | Bartek Klin |
| collection | DOAJ |
| description | We use modal logic as a framework for coalgebraic trace semantics, and show
the flexibility of the approach with concrete examples such as the language
semantics of weighted, alternating and tree automata, and the trace semantics
of generative probabilistic systems. We provide a sufficient condition under
which a logical semantics coincides with the trace semantics obtained via a
given determinization construction. Finally, we consider a condition that
guarantees the existence of a canonical determinization procedure that is
correct with respect to a given logical semantics. That procedure is closely
related to Brzozowski's minimization algorithm. |
| first_indexed | 2024-04-25T01:35:36Z |
| format | Article |
| id | doaj.art-7a7db6cf92d94252809a6e27f3c0250f |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:36Z |
| publishDate | 2017-04-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-7a7db6cf92d94252809a6e27f3c0250f2024-03-08T09:45:41ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742017-04-01Volume 12, Issue 410.2168/LMCS-12(4:10)20162622Coalgebraic trace semantics via forgetful logicsBartek Klinhttps://orcid.org/0000-0001-5793-7425Jurriaan RotWe use modal logic as a framework for coalgebraic trace semantics, and show the flexibility of the approach with concrete examples such as the language semantics of weighted, alternating and tree automata, and the trace semantics of generative probabilistic systems. We provide a sufficient condition under which a logical semantics coincides with the trace semantics obtained via a given determinization construction. Finally, we consider a condition that guarantees the existence of a canonical determinization procedure that is correct with respect to a given logical semantics. That procedure is closely related to Brzozowski's minimization algorithm.https://lmcs.episciences.org/2622/pdfcomputer science - logic in computer sciencef.3.2f.4.1 |
| spellingShingle | Bartek Klin Jurriaan Rot Coalgebraic trace semantics via forgetful logics Logical Methods in Computer Science computer science - logic in computer science f.3.2 f.4.1 |
| title | Coalgebraic trace semantics via forgetful logics |
| title_full | Coalgebraic trace semantics via forgetful logics |
| title_fullStr | Coalgebraic trace semantics via forgetful logics |
| title_full_unstemmed | Coalgebraic trace semantics via forgetful logics |
| title_short | Coalgebraic trace semantics via forgetful logics |
| title_sort | coalgebraic trace semantics via forgetful logics |
| topic | computer science - logic in computer science f.3.2 f.4.1 |
| url | https://lmcs.episciences.org/2622/pdf |
| work_keys_str_mv | AT bartekklin coalgebraictracesemanticsviaforgetfullogics AT jurriaanrot coalgebraictracesemanticsviaforgetfullogics |