Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/35523
Registo completo
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.author | Bonsangue, Marcello | por |
dc.contributor.author | Milius, Stefan | por |
dc.contributor.author | Silva, Alexandra M. | por |
dc.date.accessioned | 2015-06-09T15:51:21Z | - |
dc.date.available | 2015-06-09T15:51:21Z | - |
dc.date.issued | 2013 | - |
dc.identifier.uri | https://hdl.handle.net/1822/35523 | - |
dc.description.abstract | Coalgebras provide a uniform framework for studying dynamical systems, including several types of automata. In this article, we make use of the coalgebraic view on systems to investigate, in a uniform way, under which conditions calculi that are sound and complete with respect to behavioral equivalence can be extended to a coarser coalgebraic language equivalence, which arises from a generalized powerset construction that determinizes coalgebras. We show that soundness and completeness are established by proving that expressions modulo axioms of a calculus form the rational fixpoint of the given type functor. Our main result is that the rational fixpoint of the functor FT, where T is a monad describing the branching of the systems (e.g., non-determinism, weights, probability, etc.), has as a quotient the rational fixpoint of the determinized type functor F, a lifting of F to the category of T-algebras. We apply our framework to the concrete example of weighted automata, for which we present a new sound and complete calculus for weighted language equivalence. As a special case, we obtain nondeterministic automata in which we recover Rabinovich’s sound and complete calculus for language equivalence. | por |
dc.language.iso | eng | por |
dc.publisher | ACM | por |
dc.rights | openAccess | por |
dc.subject | Coalgebra | por |
dc.subject | Language | por |
dc.subject | Regular expressions | por |
dc.subject | Trace | por |
dc.subject | Weighted automata | por |
dc.title | Sound and complete axiomatizations of coalgebraic language equivalence | por |
dc.type | article | por |
dc.peerreviewed | yes | por |
dc.comments | 1695 | por |
sdum.publicationstatus | published | por |
oaire.citationStartPage | 1 | por |
oaire.citationEndPage | 51 | por |
oaire.citationIssue | 1 | por |
oaire.citationTitle | ACM transactions on computational logic | por |
oaire.citationVolume | 14 | por |
dc.publisher.uri | ACM | por |
dc.identifier.doi | 10.1145/2422085.2422092 | por |
sdum.journal | ACM transactions on computational logic | por |
Aparece nas coleções: | HASLab - Artigos em revistas internacionais |