Algorithms for Learning Finite Automata from Queries: A Unified View

José L. Balcázar (), Josep Díaz (), Ricard Gavaldà () and Osamu Watanabe ()
Additional contact information
José L. Balcázar: Universitat Politècnica de Catalunya, Department of Software (LSI)
Josep Díaz: Universitat Politècnica de Catalunya, Department of Software (LSI)
Ricard Gavaldà: Universitat Politècnica de Catalunya, Department of Software (LSI)
Osamu Watanabe: Tokyo Institute of Technology, Department of Computer Science

A chapter in Advances in Algorithms, Languages, and Complexity, 1997, pp 53-72 from Springer

Abstract: Abstract In this survey we compare several known variants of the algorithm for learning deterministic finite automata via membership and equivalence queries. We believe that our presentation makes it easier to understand what is going on and what the differences between the various algorithms mean. We also include the comparative analysis of the algorithms, review some known lower bounds, prove a new one, and discuss the question of parallelizing this sort of algorithm.

Keywords: Regular Language; Finite Automaton; Membership Query; Deterministic Finite Automaton; Observation Table (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3394-4_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461333944

DOI: 10.1007/978-1-4613-3394-4_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().