On the complexity of minimum inference of regular sets
From MaRDI portal
Publication:4174776
DOI10.1016/S0019-9958(78)90683-6zbMath0393.68066MaRDI QIDQ4174776
Publication date: 1978
Published in: Information and Control (Search for Journal in Brave)
Complexity; Inference; Np-Complete; Polynomial Time Algorithm; Stochastic Automata; Np-Hard; Regular Sets
Related Items
Model-based learning of interaction strategies in multi-agent systems, A natural encoding scheme proved probabilistic polynomial complete, Uniquely decodable \(n\)-gram embeddings, Prediction-preserving reducibility, Towards a general theory of topological maps, Kernel methods for learning languages, Identification of pattern languages from examples and queries, Two notions of correctness and their relation to testing, IIPS: A framework for specifying inductive-inference problems, Inferring a tree from walks, Efficient learning of typical finite automata from random walks, Map learning with uninterpreted sensors and effectors, Inference of \(\omega\)-languages from prefixes., Learning context-free grammars using tabular representations, Inference of regular languages using state merging algorithms with search, On the hardness of approximating the minimum consistent acyclic DFA and decision diagram., Inductive inference of context-free languages based on context-free expressions