We investigate a learning algorithm in the context of nominal automata, anextension of classical automata to alphabets featuring names. This class ofautomata captures nominal regular languages; analogously to the classicallanguage theory, nominal automata have been shown to characterise nominalregular expressions with binders. These formalisms are amenable to abstractmodelling resource-aware computations. We propose a learning algorithm onnominal regular languages with binders. Our algorithm generalises Angluin's L*algorithm with respect to nominal regular languages with binders. We show thecorrectness and study the theoretical complexity of our algorithm.

On Learning Nominal Automata with Binders

Emilio Tuosto
2019

Abstract

We investigate a learning algorithm in the context of nominal automata, anextension of classical automata to alphabets featuring names. This class ofautomata captures nominal regular languages; analogously to the classicallanguage theory, nominal automata have been shown to characterise nominalregular expressions with binders. These formalisms are amenable to abstractmodelling resource-aware computations. We propose a learning algorithm onnominal regular languages with binders. Our algorithm generalises Angluin's L*algorithm with respect to nominal regular languages with binders. We show thecorrectness and study the theoretical complexity of our algorithm.
cs.FL
cs.FL
Computer Science - Learning
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/10245
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact