scieee Science in your language
[en] (orig)

Sequential and parallel complexity of learning DFA

Balcázar Navarro, José Luis,Díaz Cort, Josep,Gavaldà, Ricard · 1993

Abstract

It is known that the class of deterministic finite automata is polynomial time learnable by using membership and equivalence queries. We investigate the query complexity of learning deterministic finite automata, i.e., the number of membership and equivalence queries made during the process of learning. We prove lower bounds on the number of alternations between membership and equivalence queries, and also show that a trade-off exists, allowing us to reduce the number of equivalence queries at the price of increasing the number of membership queries. Finally, we study learning in a parallel model, the CRCW PRAM. We prove a lower bound on the parallel time needed for learning and design an algorithm that asymptotically achieves this bound.

Read accessible full text

Sequential and parallel complexity of learning DFA

Author: Balcázar Navarro, José Luis,Díaz Cort, Josep,Gavaldà, Ricard
Publisher: Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
Year: 1993
Source: https://upcommons.upc.edu/bitstream/2117/372065/1/PCCNCM_93_08_Sequential%20and%20Parallel%20Complexity.pdf
Sequen ial and Pa allel Complexi y
o Lea ning DFA *
José L. Balcáza Josep Díaz Rica d Ga· alda
Dep . Llengua ges i Sis emes In o ma. ics
Uni e si a Poli ecnica Ca alunya
Pau Ga gallo 5, 08028 Ba celona, Spain
Osam·u Wa anabe
Depa n1en o Con1pu e Science
Tokyo Ins i u e o Technology
l !Iegu o-ku, Tokyo 152, Japan
Abs ac . I is known ha he class o de e minis ic ini e au oma. a is poly
no nial ime lea nable by using membe ship and equi a.lence que ies. Ve i n·es
iga e he que y complexi y o lea ning de e minis ic ini e au oma a, i.e., .he
numbe o membe ship and equi alence que ies made du ing he p ocess o lea n
ing. Ve p o e lowe bounds on he numbe o al e na ions be ween membe ship
and equi alence que ies, ancl also show ha a acle-o exis s, allowing us o e
duce he numbe o equi alence que ies a he p ice o inc easing he numbe o
membe ship que ies. Finally, we s udy lea ning in a pa a.llel moclel, he C'RC' V
PRAM. We p o e a lowe bound on he pa allel ime neeclecl o lea ning ancl
design an algo i hm ha asymp o ically achie es his bouncl.
l. In oduc ion
Que y lea ning was in oduced by Angluin [1] and is cu en ly one o he mos impo a.n
models in compu a ional lea ning heo y. I di e s om o he nodels. such as incluc i e
*This esea ch was pa ially suppo ed by he ESPRIT II Basic Resea. ch Ac ions P og a.m o he EC
unde con ac No. 3075 (p ojec ALCOM). The i s h ee au ho s we e suppo .ed in pa by .he DAAD
h ough Acciones In eg adas 1992, 131-B, 313-AI-e-es/zk. The ou h au ho was suppo ed in pa
by Takayanagi Founda ion o Elec onics and Science Technology. E-mail add esses: [email p o ec ed].
[email p o ec ed], [email p o ec ed], [email p o ec ed]
94