Paper Info
Title
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 Biichi 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.
Year
DOI
Venue
2017
10.3233/FI-2021-1999
FUNDAMENTA INFORMATICAE
Field
DocType
Volume
Continuous function,Discrete mathematics,Closure (computer programming),Automaton,Lipschitz continuity,Simulation preorder,Mathematics,Büchi automaton,Bounded function
Conference
178
Issue
ISSN
Citations 
1-2
0169-2968
0
PageRank 
References 
Authors
0.34
4
1
Name
Order
Citations
PageRank
Milka Hutagalung1133.16