Skip to Main content Skip to Navigation
Conference papers

Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata

Abstract : Coalgebra offers a general framework for modelling different types of state-based systems. Our aim is to present generic algorithms to decide behavioural equivalence for coalgebras which generalize partition refinement. The underlying idea of the algorithms is to work on the final chain and to factor out redundant information. If the algorithm terminates, the result of the construction is a representative of the given coalgebra that is not necessarily unique and that allows to precisely answer questions about behavioural equivalence. We apply the algorithm to weighted automata over semirings in order to obtain a procedure for checking language equivalence for a large number of semirings.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01402080
Contributor : Hal Ifip <>
Submitted on : Thursday, November 24, 2016 - 11:09:13 AM
Last modification on : Thursday, November 24, 2016 - 11:14:10 AM
Long-term archiving on: : Monday, March 27, 2017 - 9:15:25 AM

File

978-3-662-44602-7_24_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Barbara König, Sebastian Küpper. Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.311-325, ⟨10.1007/978-3-662-44602-7_24⟩. ⟨hal-01402080⟩

Share

Metrics

Record views

379

Files downloads

203