Polynomial characteristic sets for DFA identification

descriptionPublicationkeyboard_double_arrow_right Article 01 Aug 2012 English Publisher:Elsevier BVJournal:Theoretical Computer Science, volume 448, pages 41-46 (issn: 0304-3975,

Copyright policy )

Authors: Pedro García 0001; Damián López; Manuel Vazquez de Parga;

doi: 10.1016/j.tcs.2012.04.042

Polynomial characteristic sets for DFA identification

- Summary
- Subjects
- Metrics

Abstract

[EN] We study the order in Grammatical Inference algorithms, and its influence on the polynomial (with respect to the data) identification of languages. This work is motivated by recent results on the polynomial convergence of data-driven grammatical inference algorithms. In this paper, we prove a sufficient condition that assures the existence of a characteristic sample whose size is polynomial with respect to the minimum DFA of the target language. © 2012 Elsevier B.V. All rights reserved.

Work partially supported by the Spanish Ministerio de Economia y Competitividad under research project TIN2011-28260-C03-01 and Universidad Politecnica de Valencia grant PAID-2019-06-2011.

Related Organizations

Universitat Politècnica de València
Spain

Keywords

Computational learning theory, Theoretical Computer Science, Grammatical inference, grammatical inference, Target language, Grammars and rewriting systems, DFA identification, LENGUAJES Y SISTEMAS INFORMATICOS, Grammatical inferences, Algorithms, Computer Science(all)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average