Learning from positive and negative examples: new proof for binary alphabets

DOI10.1016/j.ipl.2023.106427zbMath1529.68125arXiv2206.10025OpenAlexW4382933103MaRDI QIDQ6072211

Mateus de Oliveira Oliveira, Petra Wolf, Jonas Lingg

Publication date: 12 October 2023

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitylearning automatafinite samples

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization technique based on learning automata
• Recent advances in learning automata
• Learning deterministic probabilistic automata from a model checking perspective
• A note on learning automata-based schemes for adaptation of BP parameters
• A multi-parameter analysis of hard problems on deterministic finite automata
• Supervisory Control of a Class of Discrete Event Processes
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Complexity of automaton identification from given data
• On the complexity of minimum inference of regular sets
• Language identification in the limit
• Learning DFA from simple examples

This page was built for publication: Learning from positive and negative examples: new proof for binary alphabets