Publications

Publications by Alexandra Silva

2014

Algebra-Coalgebra Duality in Brzozowski's Minimization Algorithm

Authors
Bonchi, F; Bonsangue, MM; Hansen, HH; Panangaden, P; Rutten, JJMM; Silva, A;

Publication
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC

Abstract
We give a new presentation of Brzozowski's algorithm to minimize finite automata using elementary facts from universal algebra and coalgebra and building on earlier work by Arbib and Manes on a categorical presentation of Kalman duality between reachability and observability. This leads to a simple proof of its correctness and opens the door to further generalizations. Notably, we derive algorithms to obtain minimal language equivalent automata from Moore nondeterministic and weighted automata.

CloseRead Abstract

2016

Report on the POPL mentoring workshop (PLMW 2016)

Authors
Silva, A;

Publication
SIGLOG News

Abstract

2014

Preface

Authors
Jacobs, B; Silva, A; Staton, S;

Publication
Electronic Notes in Theoretical Computer Science

Abstract

2013

Language Constructs for Non-Well-Founded Computation

Authors
Jeannin, JB; Kozen, D; Silva, A;

Publication
Programming Languages and Systems - 22nd European Symposium on Programming, ESOP 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings

Abstract

2014

A coalgebraic view on decorated traces

Authors
BONCHI, F; BONSANGUE, M; CALTAIS, G; RUTTEN, J; SILVA, A;

Publication
Mathematical Structures in Computer Science

Abstract

2013

Brzozowski's and up-to algorithms for must testing

Authors
Bonchi, F; Caltais, G; Pous, D; Silva, A;

Publication
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Abstract
Checking language equivalence (or inclusion) of finite automata is a classical problem in Computer Science, which has recently received a renewed interest and found novel and more effective solutions, such as approaches based on antichains or bisimulations up-to. Several notions of equivalence (or preorder) have been proposed for the analysis of concurrent systems. Usually, the problem of checking these equivalences is reduced to checking bisimilarity. In this paper, we take a different approach and propose to adapt algorithms for language equivalence to check one prime equivalence in concurrency theory, must testing semantics. To achieve this transfer of technology from language to must semantics, we take a coalgebraic outlook at the problem. © Springer International Publishing 2013.

CloseRead Abstract