---
res:
bibo_abstract:
- 'One central issue in the formal design and analysis of reactive systems is the
notion of refinement that asks whether all behaviors of the implementation is
allowed by the specification. The local interpretation of behavior leads to the
notion of simulation. Alternating transition systems (ATSs) provide a general
model for composite reactive systems, and the simulation relation for ATSs is
known as alternating simulation. The simulation relation for fair transition systems
is called fair simulation. In this work our main contributions are as follows:
(1) We present an improved algorithm for fair simulation with Büchi fairness constraints;
our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time
algorithm, where n is the number of states and m is the number of transitions.
(2) We present a game based algorithm for alternating simulation that requires
O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where
n is the number of states and m is the size of transition relation. (3) We present
an iterative algorithm for alternating simulation that matches the time complexity
of the game based algorithm, but is more space efficient than the game based algorithm.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Siddhesh
foaf_name: Chaubal, Siddhesh
foaf_surname: Chaubal
- foaf_Person:
foaf_givenName: Pritish
foaf_name: Kamath, Pritish
foaf_surname: Kamath
bibo_doi: 10.15479/AT:IST-2012-0001
dct_date: 2012^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2664-1690
dct_language: eng
dct_publisher: IST Austria@
dct_title: Faster algorithms for alternating refinement relations@
...