Alexandra Silva

TCS Journal 2025 Journal Article

Convex language semantics for nondeterministic probabilistic automata

• Gerco van Heerdt
• Justin Hsu
• Joël Ouaknine
• Alexandra Silva

We explore language semantics for automata combining probabilistic and nondeterministic behaviors. We first show that there are precisely two natural semantics for probabilistic automata with nondeterminism. For both choices, we show that these automata are strictly more expressive than deterministic probabilistic automata, and we prove that the problem of checking language equivalence is undecidable by reduction from the threshold problem. However, we provide a discounted metric that can be computed to arbitrarily high precision.

GandALF Workshop 2023 Workshop Paper

Conflict-Aware Active Automata Learning

• Tiago Ferreira
• Léo Henry
• Raquel Fernandes da Silva
• Alexandra Silva

Active automata learning algorithms cannot easily handle conflict in the observation data (different outputs observed for the same inputs). This inherent inability to recover after a conflict impairs their effective applicability in scenarios where noise is present or the system under learning is mutating. We propose the Conflict-Aware Active Automata Learning (C3AL) framework to enable handling conflicting information during the learning process. The core idea is to consider the so-called observation tree as a first-class citizen in the learning process. Though this idea is explored in recent work, we take it to its full effect by enabling its use with any existing learner and minimizing the number of tests performed on the system under learning, specially in the face of conflicts. We evaluate C3AL in a large set of benchmarks, covering over 30 different realistic targets, and over 18, 000 different scenarios. The results of the evaluation show that C3AL is a suitable alternative framework for closed-box learning that can better handle noise and mutations.

TCS Journal 2020 Journal Article

Left-handed completeness

• Dexter Kozen
• Alexandra Silva

We give a new proof of the completeness of the left-handed star rule of Kleene algebra. The proof is significantly shorter than previous proofs and exposes the rich interaction of algebra and coalgebra in the theory of Kleene algebra.

TCS Journal 2015 Journal Article

Killing epsilons with a dagger: A coalgebraic study of systems with algebraic label structure

• Filippo Bonchi
• Stefan Milius
• Alexandra Silva
• Fabio Zanasi

We propose an abstract framework for modelling state-based systems with internal behaviour as e. g. given by silent or ϵ-transitions. Our approach employs monads with a parametrized fixpoint operator † to give a semantics to those systems and implement a sound procedure of abstraction of the internal transitions, whose labels are seen as the unit of a free monoid. More broadly, our approach extends the standard coalgebraic framework for state-based systems by taking into account the algebraic structure of the labels of their transitions. This allows to consider a wide range of other examples, including Mazurkiewicz traces for concurrent systems and non-deterministic transducers.

TCS Journal 2011 Journal Article

Preface

• Bart Jacobs
• Milad Niqui
• Jan Rutten
• Alexandra Silva