Learning weighted automata over principal ideal domains

DOI10.1007/978-3-030-45231-5_31MaRDI QIDQ2200852zbMATH OpenOpenAlexFDO

Authors Gerco van Heerdt, Clemens Kupke, Jurriaan Rot, Alexandra Silva

Publication date 23 September 2020

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Hankel matrixactive learningMAT learningprincipal ideal domainweighted automatonobservation-table learning

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational learning theory (68Q32)

Abstract: In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin's seminal LStar algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.

Recommendations

• Weighted automata are compact and actively learnable
• Learning Deterministically Recognizable Tree Series — Revisited
• Learning deterministic automata on infinite words
• Learning weighted automata
• Generalization bounds for learning weighted automata

Cites work

• scientific article; zbMATH DE number 3085223 (Why is no real title available?)
• CALF: categorical automata learning framework
• Formal Analysis of Online Algorithms
• Learning Behaviors of Automata from Multiplicity and Equivalence Queries
• Learning nominal automata
• Learning register automata with fresh value generation
• Learning regular sets from queries and counterexamples
• Learning weighted automata
• Matrices de Hankel
• On the learnability of infinitary regular sets
• Onto Endomorphisms are Isomorphisms
• Parametrized recurrent systems for image generation
• Realizations by stochastic finite automata
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• The design principles of a weighted finite-state transducer library
• Weighted Bisimulation in Linear Algebraic Form
• \(L^\ast\)-based learning of Markov decision processes (extended version)

Cited in

(9)

• KI 2004: Advances in Artificial Intelligence
• A categorical framework for learning generalised tree automata
• Combining semilattices and semimodules
• Learning pomset automata
• Learning of Structurally Unambiguous Probabilistic Grammars
• Generalization bounds for learning weighted automata
• A new approach for active automata learning based on apartness
• Weighted automata are compact and actively learnable
• Deterministic weighted automata under partial observability

This page was built for publication: Learning weighted automata over principal ideal domains

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