What is the search space of Regular Inference?
(1994) Grammatical Inference and Applications, Alicante, Spain, September 21-23, 1994 — ISBN: [3-540-58473-0], p. 25-37, published
Files
what.pdf
Restricted Access - Adobe PDF
- 747.37 KB
Details
- Authors
- Abstract
- This paper revisits the theory of regular inference, in particular by extending the definition of structural completeness of a positive sample and by demonstrating two basic theorems. This framework enables to state the regular inference problem as a search through a boolean lattice built from the positive sample. Several properties of the search space are studied and generalization criteria are discussed. In this framework, the concept of border set is introduced, that is the set of the most general solutions excluding a negative sample. Finally, the complexity of regular language identification from both a theoritic al and a practical point of view is discussed.
- Affiliations
France TELECOM Ecole Nationale Supérieure de Sciences Appliquées et Technologie - IRISA Universidad Politecnica de Valencia DSIC -
Citations
Dupont, P., Miclet, L., & Vidal, E. (1994). What is the search space of Regular Inference? In R. Carrasco, J. Oncina (ed.), Grammatical Inference and Applications, Alicante, Spain, September 21-23, 1994 (p. p. 25-37). Springer-Verlag. https://hdl.handle.net/2078.5/253817