Nondeterministic automata: equivalence, bisimulations, and uniform relations

Details Nondeterministic automata: equivalence, bisimulations, and uniform relations Nondeterministic automata: equivalence, bisimulations, and uniform relations

2011-02-26

arxiv.org/abs/1102.5449v1

Computer Science

Formal Languages and Automata Theory

35 pages, submitted to Computers and Mathematics with Applications

Scientific paper

In this paper we study the equivalence of nondeterministic automata pairing the concept of a bisimulation with the recently introduced concept of a uniform relation. In this symbiosis, uniform relations serve as equivalence relations which relate states of two possibly different nondeterministic automata, and bisimulations ensure compatibility with the transitions, initial and terminal states of these automata. We define six types of bisimulations, but due to the duality we discuss three of them: forward, backward-forward, and weak forward bisimulations. For each od these three types of bisimulations we provide a procedure which decides whether there is a bisimulation of this type between two automata, and when it exists, the same procedure computes the greatest one. We also show that there is a uniform forward bisimulation between two automata if and only if the factor automata with respect to the greatest forward bisimulation equivalences on these automata are isomorphic. We prove a similar theorem for weak forward bisimulations, using the concept of a weak forward isomorphism instead of an isomorphism. We also give examples that explain the relationships between the considered types of bisimulations.

Affiliated with

Also associated with

No associations

Rating

Nondeterministic automata: equivalence, bisimulations, and uniform relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nondeterministic automata: equivalence, bisimulations, and uniform relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nondeterministic automata: equivalence, bisimulations, and uniform relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-53671