Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Learning probabilistic automata : a study in state distinguishability

Autor
B. Balle; Castro, J.; Gavaldà, R.
Tipus d'activitat
Article en revista
Revista
Theoretical computer science
Data de publicació
2013-02-18
Volum
473
Pàgina inicial
46
Pàgina final
60
DOI
https://doi.org/10.1016/j.tcs.2012.10.009 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/18260 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0304397512009309 Obrir en finestra nova
Resum
Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability μ of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on μ is necessary in the worst case for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed View the MathML source-queries is defined. We show how to simulate View the MathML source...
Citació
B. Balle; Castro, J.; Gavaldà, R. Learning probabilistic automata : a study in state distinguishability. "Theoretical computer science", 18 Febrer 2013, vol. 473, p. 46-60.
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants