Milka Hutagalung

dblp:127/3633 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 1 since 2021
YearPublicationVenuePosition
2021 Topological Characterisation of Multi-Buffer Simulation
abstract
Multi-buffer simulation is an extension of simulation preorder that can be used to approximate inclusion of languages recognised by Büchi automata up to their trace closures. DUPLICATOR can use some bounded or unbounded buffers to simulate SPOILER’s move. It has been shown that multi-buffer simulation can be characterised with the existence of a continuous function. In this paper, we show that such a characterisation can be refined to a more restricted case, that is, to the one where DUPLICATOR only uses bounded buffers, by requiring the function to be Lipschitz continuous instead of only continuous. This characterisation however only holds for some restricted classes of automata. One of the automata should only produce words where each letter cannot commute unboundedly. We show that this property can be syntactically characterised with cyclic-path-connectedness, a refinement of syntactic condition on automata that have regular trace closure. We further show that checking cyclic-path-connectedness is indeed co-NP-complete.
Milka Hutagalung
Fundam. Informaticae1
2018 Multi-buffer simulations: Decidability and complexity
Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange 0001, Étienne Lozes
Inf. Comput.1
2013 Revealing vs. Concealing: More Simulation Games for Büchi Inclusion
Milka Hutagalung, Martin Lange 0001, Étienne Lozes
LATA1