On the complexity of minimum inference of regular sets
From MaRDI portal
Publication:4174776
DOI10.1016/S0019-9958(78)90683-6zbMath0393.68066OpenAlexW2018706164MaRDI QIDQ4174776
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 revisited ⋮ On the hardness of approximating the minimum consistent OBDD problem ⋮ Identification of pattern languages from examples and queries ⋮ Inferring a tree from walks ⋮ A natural encoding scheme proved probabilistic polynomial complete ⋮ Efficient learning of typical finite automata from random walks ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ Minimal consistent DFA from sample strings ⋮ Learning Weighted Automata ⋮ Learning from positive and negative examples: new proof for binary alphabets ⋮ On the complexity of automatic complexity ⋮ Map learning with uninterpreted sensors and effectors ⋮ Learning Grammars and Automata with Queries ⋮ On the Inference of Finite State Automata from Positive and Negative Data ⋮ Two notions of correctness and their relation to testing ⋮ Inference of \(\omega\)-languages from prefixes. ⋮ Regular inference as vertex coloring ⋮ Inductive inference of context-free languages based on context-free expressions ⋮ Kernel methods for learning languages ⋮ IIPS: A framework for specifying inductive-inference problems ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Learning context-free grammars using tabular representations ⋮ Inference of regular languages using state merging algorithms with search ⋮ Uniquely decodable \(n\)-gram embeddings ⋮ Unnamed Item ⋮ Model-based learning of interaction strategies in multi-agent systems ⋮ A sufficient condition to polynomially compute a minimum separating DFA ⋮ Types of Trusted Information That Make DFA Identification with Correction Queries Feasible ⋮ Prediction-preserving reducibility ⋮ The Complexity of Fixed-Height Patterned Tile Self-assembly ⋮ Inferring a tree from walks ⋮ On 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
