COMPUTING THE RABIN INDEX OF A REGULAR LANGUAGE OF INFINITE WORDS

Authors
WILKE T YOO H
Citation
T. Wilke et H. Yoo, COMPUTING THE RABIN INDEX OF A REGULAR LANGUAGE OF INFINITE WORDS, Information and computation, 130(1), 1996, pp. 61-70
Citations number
10
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
130
Issue
1
Year of publication
1996
Pages
61 - 70
Database
ISI
SICI code
0890-5401(1996)130:1<61:CTRIOA>2.0.ZU;2-O
Abstract
The Rabin index of a regular language of infinite words is the minimum number of accepting pairs used in any deterministic Rabin automaton r ecognizing this language. We show that the Rabin index of a language g iven by a Muller automaton with n states and m accepting sets is compu table in time O(m(2)nc) where c is the cardinality of the alphabet. (C ) 1996 Academic Press, Inc.