ON THE LEARNABILITY OF INFINITARY REGULAR SETS

Authors
MALER O PNUELI A
Citation
O. Maler et A. Pnueli, ON THE LEARNABILITY OF INFINITARY REGULAR SETS, Information and computation, 118(2), 1995, pp. 316-326
Citations number
35
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
118
Issue
2
Year of publication
1995
Pages
316 - 326
Database
ISI
SICI code
0890-5401(1995)118:2<316:OTLOIR>2.0.ZU;2-9
Abstract
In this paper we extend the automaton synthesis paradigm to infinitary languages, that is, to subsets of the set Sigma(omega) of all infinit e sequences over some alphabet Sigma. Our main result is a polynomial algorithm for learning a sub-class of the omega-regular sets from memb ership queries and counter-examples based on the framework suggested b y Angluin (Angluin, D. (1987), Inform. and Comput. 75, 87-106) for lea rning regular subsets of Sigma. (C) 1995 Academic Press, Inc.