Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata

Details Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata

2010-07-08

arxiv.org/abs/1007.1333v2

Computer Science

Formal Languages and Automata Theory

Scientific paper

In this report we study the problem of minimising deterministic automata over finite and infinite words. Deterministic finite automata are the simplest devices to recognise regular languages, and deterministic Buchi, Co-Buchi, and parity automata play a similar role in the recognition of \omega-regular languages. While it is well known that the minimisation of deterministic finite and weak automata is cheap, the complexity of minimising deterministic Buchi and parity automata has remained an open challenge. We establish the NP-completeness of these problems. A second contribution of this report is the introduction of relaxed minimisation of deterministic finite automata. Like hyper-minimisation, relaxed minimisation allows for some changes in the language of the automaton: We seek a smallest automaton that, when used as a monitor, provides a wrong answer only a bounded number of times in any run of a system. We argue that minimisation of finite automata, hyper-minimisation, relaxed minimisation, and the minimisation of deterministic Buchi (or Co-Buchi) automata are operations of increasing reduction power, as the respective equivalence relations on automata become coarser from left to right. When we allow for minor changes in the language, relaxed minimisation can therefore be considered as a more powerful minimisation technique than hyper-minimisation from the perspective of finite automata. From the perspective of Buchi and Co-Buchi automata, we gain a cheap algorithm for state-space reduction that also turns out to be beneficial for further heuristic or exhaustive state-space reductions put on top of it.

Affiliated with

Also associated with

No associations

Rating

Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata 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 Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-102744