Learning nominal automata

DOI10.1145/3009837.3009879MaRDI QIDQ5370894zbMATH OpenOpenAlexWikidataFDO

Authors Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, Michał Szynwelski

Publication date 20 October 2017

Published in Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.06268

zbMATH Keywords

functional programmingactive learningnominal automata(non)deterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational learning theory (68Q32) Functional programming and lambda calculus (68N18)

Abstract: We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting. In particular we can learn a subclass of nominal non-deterministic automata. An implementation using a recently developed Haskell library for nominal computation is provided for preliminary experiments.

Recommendations

• Fast computations on ordered nominal sets
• Automata theory in nominal sets
• A generic algorithm for learning symbolic automata from membership queries
• Learning symbolic automata
• Universal automata and NFA learning

Cited in

(35)

• Nominal automata with name binding
• Learning weighted automata over principal ideal domains
• A categorical framework for learning generalised tree automata
• Learning pomset automata
• Approximate learning of limit-average automata
• Learning infinite-word automata with loop-index queries
• scientific article; zbMATH DE number 7559500 (Why is no real title available?)
• A (co)algebraic theory of succinct automata
• Polynomial-time equivalence testing for deterministic fresh-register automata
• Completeness of Nominal PROPs
• A generic algorithm for learning symbolic automata from membership queries
• A novel learning algorithm for Büchi automata based on family of DFAs and classification trees
• Guarded Kleene algebra with tests: automata learning
• Active learning for deterministic bottom-up nominal tree automata
• Learning automata and transducers: a categorical approach
• What you must remember when transforming datawords
• Learning symbolic automata
• On-the-fly bisimilarity checking for fresh-register automata
• A Myhill-Nerode theorem for register automata and symbolic trace languages
• Fast computations on ordered nominal sets
• Automata theory in nominal sets
• Passive learning of regular data languages in polynomial time and data
• Fast computations on ordered nominal sets
• Active learning for sound negotiations
• Complete test suites for automata in monoidal closed categories
• scientific article; zbMATH DE number 7471718 (Why is no real title available?)
• Variable automata over infinite alphabets
• Compositional automata learning of synchronous systems
• Completeness and incompleteness in nominal Kleene algebra
• Automata and grammars for data words
• Feasability of learning weighted automata on a semiring
• A new approach for active automata learning based on apartness
• Learning deterministic variable automata over infinite alphabets
• Nominal automata for resource usage control
• CALF: categorical automata learning framework

Describes a project that uses

Uses Software

• NLambda
• Sigma*
• LOIS
• z3
• Haskell

This page was built for publication: Learning nominal automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370894)