Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries

Giovanna MelideoContact Information and Stefano VarricchioContact Information

(5)  Dipartimento di Matematica Pura ed Applicata, Universita’ di L’Aquila, Via Vetoio, I-67100 L’Aquila, Italy
Abstract
We investigate the learning problem of unary output two-tape non deterministic finite automata (unary output 2-tape NFAs) from multiplicity and equivalence queries. Given an alphabet A and a unary alphabet x, a unary output 2-tape NFA accepts a subset of AA *xx *. In [6] Bergadano and Varricchio proved that the behavior of an unknown automaton with multiplicity in a field K (K-automaton) is exactly identifiable when multiplicity and equivalence queries are allowed. In this paper multiplicity automata are used to prove the learnability of unary output 2-tape NFA’s. We shall identify the behavior of a unary output 2-tape NFA using an automaton with multiplicity in K rat 〈〈x〉〉. We provide an algorithm which is polynomial in the size of this automaton.

Contact Information Giovanna Melideo
Email: melideo@univaq.it

Contact Information Stefano Varricchio
Email: varricch@univaq.it
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb05
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)