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

DOI10.1016/J.IPL.2023.106427MaRDI QIDQ6072211zbMATH OpenOpenAlexFDO

Authors Jonas Lingg, Mateus de Oliveira Oliveira, Petra Wolf

Publication date 12 October 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexityfinite sampleslearning automata

Mathematics Subject Classification ID

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

Abstract: One of the most fundamental problems in computational learning theory is the the problem of learning a finite automaton $A$ consistent with a finite set $P$ of positive examples and with a finite set $N$ of negative examples. By consistency, we mean that $A$ accepts all strings in $P$ and rejects all strings in $N$. It is well known that this problem is NP-complete. In the literature, it is stated that this NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. But as a crucial detail, the work of Gold actually considered Mealy machines and not deterministic finite state automata (DFAs) as they are considered nowadays. As Mealy automata are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptions of Gold's construction for Mealy machines stated in the literature have some issues and give a new construction for DFAs with a binary alphabet ourselves.

Recommendations

• Learning unary automata
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Three \(\sum^ P_ 2\)-complete problems in computational learning theory
• Learning deterministic finite automata from smallest counterexamples
• scientific article; zbMATH DE number 1303603

Cites work

• A multi-parameter analysis of hard problems on deterministic finite automata
• A note on learning automata-based schemes for adaptation of BP parameters
• Complexity of automaton identification from given data
• Grammatical inference. Learning automata and grammars.
• scientific article; zbMATH DE number 2080060 (Why is no real title available?)
• Language identification in the limit
• Learning deterministic probabilistic automata from a model checking perspective
• Learning DFA from simple examples
• On the complexity of minimum inference of regular sets
• Optimization technique based on learning automata
• Recent advances in learning automata
• Supervisory Control of a Class of Discrete Event Processes
• The minimum consistent DFA problem cannot be approximated within any polynomial

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

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