Learning weighted automata over principal ideal domains

DOI10.1007/978-3-030-45231-5_31zbMATH Open1461.68093arXiv1911.04404OpenAlexW3023251497MaRDI QIDQ2200852FDOQ2200852

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

Publication date: 23 September 2020

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.

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

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

zbMATH Keywords

Hankel matrixactive learningMAT learningprincipal ideal domainweighted automatonobservation-table learning

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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
• Deterministic weighted automata under partial observability
• Weighted automata are compact and actively learnable
• KI 2004: Advances in Artificial Intelligence

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)