Büchi Automata can have Smaller Quotients

Details Büchi Automata can have Smaller Quotients Büchi Automata can have Smaller Quotients

2011-02-16

arxiv.org/abs/1102.3285v2

Computer Science

Formal Languages and Automata Theory

technical report of a ICALP 2011 paper

Scientific paper

We study novel simulation-like preorders for quotienting nondeterministic B\"uchi automata. We define fixed-word delayed simulation, a new preorder coarser than delayed simulation. We argue that fixed-word simulation is the coarsest forward simulation-like preorder which can be used for quotienting B\"uchi automata, thus improving our understanding of the limits of quotienting. Also, we show that computing fixed-word simulation is PSPACE-complete. On the practical side, we introduce proxy simulations, which are novel polynomial-time computable preorders sound for quotienting. In particular, delayed proxy simulation induce quotients that can be smaller by an arbitrarily large factor than direct backward simulation. We derive proxy simulations as the product of a theory of refinement transformers: A refinement transformer maps preorders non-decreasingly, preserving certain properties. We study under which general conditions refinement transformers are sound for quotienting.

Affiliated with

Also associated with

No associations

Rating

Büchi Automata can have Smaller Quotients 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 Büchi Automata can have Smaller Quotients, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Büchi Automata can have Smaller Quotients will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-416954