SCIENCE@home

Fair Simulation for Nondeterministic and Probabilistic Buechi Automata: a Coalgebraic Perspective

Natsuki Urabe,I. Hasuo

Published 2016 in Log. Methods Comput. Sci.

ABSTRACT

Notions of simulation, among other uses, provide a computationally tractable and sound (but not necessarily complete) proof method for language inclusion. They have been comprehensively studied by Lynch and Vaandrager for nondeterministic and timed systems; for B\"{u}chi automata the notion of fair simulation has been introduced by Henzinger, Kupferman and Rajamani. We contribute to a generalization of fair simulation in two different directions: one for nondeterministic tree automata previously studied by Bomhard; and the other for probabilistic word automata with finite state spaces, both under the B\"{u}chi acceptance condition. The former nondeterministic definition is formulated in terms of systems of fixed-point equations, hence is readily translated to parity games and is then amenable to Jurdzi\'{n}ski's algorithm; the latter probabilistic definition bears a strong ranking-function flavor. These two different-looking definitions are derived from one source, namely our coalgebraic modeling of B\"{u}chi automata. Based on these coalgebraic observations, we also prove their soundness: a simulation indeed witnesses language inclusion.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-49 of 49 references · Page 1 of 1

CITED BY