Michaliszyn, Jakub ;
Otop, Jan
Approximate Learning of LimitAverage Automata
Abstract
Limitaverage automata are weighted automata on infinite words that use average to aggregate the weights seen in infinite runs. We study approximate learning problems for limitaverage automata in two settings: passive and active. In the passive learning case, we show that limitaverage automata are not PAClearnable as samples must be of exponentialsize to provide (with good probability) enough details to learn an automaton. We also show that the problem of finding an automaton that fits a given sample is NPcomplete. In the active learning case, we show that limitaverage automata can be learned almostexactly, i.e., we can learn in polynomial time an automaton that is consistent with the target automaton on almost all words. On the other hand, we show that the problem of learning an automaton that approximates the target automaton (with perhaps fewer states) is NPcomplete. The abovementioned results are shown for the uniform distribution on words. We briefly discuss learning over different distributions.
BibTeX  Entry
@InProceedings{michaliszyn_et_al:LIPIcs:2019:10919,
author = {Jakub Michaliszyn and Jan Otop},
title = {{Approximate Learning of LimitAverage Automata}},
booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)},
pages = {17:117:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771214},
ISSN = {18688969},
year = {2019},
volume = {140},
editor = {Wan Fokkink and Rob van Glabbeek},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10919},
URN = {urn:nbn:de:0030drops109198},
doi = {10.4230/LIPIcs.CONCUR.2019.17},
annote = {Keywords: weighted automata, learning, expected value}
}
2019
Keywords: 

weighted automata, learning, expected value 
Seminar: 

30th International Conference on Concurrency Theory (CONCUR 2019)

Issue date: 

2019 
Date of publication: 

2019 