NDLI: Learning Deterministic Finite Automata from Smallest Counterexamples

Please wait, while we are loading the content...

Learning Deterministic Finite Automata from Smallest Counterexamples

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Bker, Andreas Birkendorf, Andreas Simon, Hans Ulrich
Copyright Year	2000
Abstract	We show in this paper (which appeared in a preliminary form as an extended abstract in [Proceedings of the 9th International ACM--SIAM Symposium on Discrete Algorithms, ACM, 1998]) that deterministic finite automata (DFAs) with n states and input alphabet $\Sigma$ can efficiently be learned from less than $\|\Sigma\|n^2$ smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required $\|\Sigma\|n^3$ smallest counterexamples. We present a general strategy which learns a finite concept class ${\cal F}$ from $\lfloor\log{\cal F}\rfloor$ smallest counterexamples (but not necessarily efficiently). An application to DFAs with at most n states shows that $(1+o(1))\|\Sigma\|n\log n$ smallest counterexamples are sufficient (if efficiency is not an issue). We show next that the special DFAs operating on input words of an arbitrary but fixed length (the so-called leveled DFAs) are efficiently learnable from $(1+o(1))\|\Sigma\|n\log n$ smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required $\|\Sigma\|n^2$ smallest counterexamples. Furthermore, we present a general lower bound on the number of smallest counterexamples (required by any learning algorithm). This bound can be stated in terms of a (new) combinatorial dimension associated with the target class. A computation of this dimension for leveled or arbitrary DFAs leads to a lower bound of the form $(\frac{1}{4}+o(1))\|\Sigma\|n\log n$. This bound matches the aforementioned upper bounds modulo a constant of approximately 4. Finally, we present a general conversion of algorithms learning from smallest counterexamples into algorithms performing self-directed learning. Forthe particular classes of leveled or arbitrary DFAs, this conversion leads to self-directed learners making the smallest possible number of mistakes (modulo a constant of approximately 4). A similar remark is valid for the class of multiplicity automata (MAs).
Starting Page	465
Ending Page	491
Page Count	27
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480198340943
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	13
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	self-directed learning multiplicity automata deterministic finite automata Computational learning theory learning from smallest counterexamples
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Learning deterministic finite automata from smallest counterexamples

Learning Deterministic Finite Automata from Smallest Counterexamples (2000)

Learning Non-deterministic Finite Automata from Queries and Counterexamples (1993)

Learning Behaviors of Automata from Multiplicity and Equivalence Queries

Improvement multiplicity of routs in directed diffusion by learning automata new approach in directed diffusion

Multi-head Watson–Crick automata

Note on the complexity of Las Vegas automata problems

Mining decision rules from deterministic finite automata

Learning nominal automata

Learning Deterministic Finite Automata from Smallest Counterexamples

Similar Documents

Learning deterministic finite automata from smallest counterexamples

Learning Deterministic Finite Automata from Smallest Counterexamples (2000)

Learning Non-deterministic Finite Automata from Queries and Counterexamples (1993)

Learning Behaviors of Automata from Multiplicity and Equivalence Queries

Improvement multiplicity of routs in directed diffusion by learning automata new approach in directed diffusion

Multi-head Watson–Crick automata

Note on the complexity of Las Vegas automata problems

Mining decision rules from deterministic finite automata

Learning nominal automata

Learning Deterministic Finite Automata from Smallest Counterexamples