García Gómez, P.; López Rodríguez, D.; Vázquez-De-Parga Andrade, M. (2012). Polynomial characteristic sets for DFA identification. Theoretical Computer Science. 448:41-46. https://doi.org/10.1016/j.tcs.2012.04.042
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/37983
Title:
|
Polynomial characteristic sets for DFA identification
|
Author:
|
García Gómez, Pedro
López Rodríguez, Damián
Vázquez-De-Parga Andrade, Manuel
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació
|
Issued date:
|
|
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 ...[+]
[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.
[-]
|
Subjects:
|
DFA identification
,
Grammatical inference
,
Grammatical inferences
,
Target language
,
Algorithms
|
Copyrigths:
|
Reserva de todos los derechos
|
Source:
|
Theoretical Computer Science. (issn:
0304-3975
)
|
DOI:
|
10.1016/j.tcs.2012.04.042
|
Publisher:
|
Elsevier
|
Publisher version:
|
http://doi.org/10.1016/j.tcs.2012.04.042
|
Project ID:
|
info:eu-repo/grantAgreement/MICINN//TIN2011-28260-C03-01/ES/REDES DE PROCESADORES BIO-INSPIRADOS: RESULTADOS TEORICOS, IMPLEMENTACION HARDWARE%2FBIOWARE, DESARROLLO SOFTWARE Y SOLUCION PARA APLICACIONES/
info:eu-repo/grantAgreement/UPV//PAID-2019-06-2011/
|
Thanks:
|
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.
|
Type:
|
Artículo
|