On the complexity of minimum inference of regular sets

From MaRDI portal
Publication:4174776

DOI10.1016/S0019-9958(78)90683-6zbMath0393.68066OpenAlexW2018706164MaRDI QIDQ4174776

Dana Angluin

Publication date: 1978

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(78)90683-6




Related Items (33)

Minimal consistent DFA revisitedOn the hardness of approximating the minimum consistent OBDD problemIdentification of pattern languages from examples and queriesInferring a tree from walksA natural encoding scheme proved probabilistic polynomial completeEfficient learning of typical finite automata from random walksLearning from positive and negative examples: dichotomies and parameterized algorithmsMinimal consistent DFA from sample stringsLearning Weighted AutomataLearning from positive and negative examples: new proof for binary alphabetsOn the complexity of automatic complexityMap learning with uninterpreted sensors and effectorsLearning Grammars and Automata with QueriesOn the Inference of Finite State Automata from Positive and Negative DataTwo notions of correctness and their relation to testingInference of \(\omega\)-languages from prefixes.Regular inference as vertex coloringInductive inference of context-free languages based on context-free expressionsKernel methods for learning languagesIIPS: A framework for specifying inductive-inference problemsA multi-parameter analysis of hard problems on deterministic finite automataLearning context-free grammars using tabular representationsInference of regular languages using state merging algorithms with searchUniquely decodable \(n\)-gram embeddingsUnnamed ItemModel-based learning of interaction strategies in multi-agent systemsA sufficient condition to polynomially compute a minimum separating DFATypes of Trusted Information That Make DFA Identification with Correction Queries FeasiblePrediction-preserving reducibilityThe Complexity of Fixed-Height Patterned Tile Self-assemblyInferring a tree from walksOn the hardness of approximating the minimum consistent acyclic DFA and decision diagram.Towards a general theory of topological maps




This page was built for publication: On the complexity of minimum inference of regular sets