Complexity of automaton identification from given data
From MaRDI portal
Publication:4153610
DOI10.1016/S0019-9958(78)90562-4zbMath0376.68041WikidataQ56620635 ScholiaQ56620635MaRDI QIDQ4153610
Publication date: 1978
Published in: Information and Control (Search for Journal in Brave)
Related Items
Learning from positive and negative examples: new proof for binary alphabets, Learning reward machines: a study in partially observable reinforcement learning, Controlling entity integrity with key sets, Inferring Symbolic Automata, Passive automata learning: DFAs and NFAs, Unnamed Item, Learning of Structurally Unambiguous Probabilistic Grammars, Bounded degree graph inference from walks, Minimal consistent DFA revisited, On the hardness of approximating the minimum consistent OBDD problem, Autonomous agents modelling other agents: a comprehensive survey and open problems, Identification of pattern languages from examples and queries, Learning regular sets from queries and counterexamples, Inferring a tree from walks, Circuit lower bounds from learning-theoretic approaches, Certifying DFA bounds for recognition and separation, LARS: a learning algorithm for rewriting systems, Inferring regular languages and \(\omega\)-languages, Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas, Inductive inference of ultimately periodic sequences, Efficient learning of typical finite automata from random walks, Learning from positive and negative examples: dichotomies and parameterized algorithms, Tree Containment With Soft Polytomies, On the minimization of XML schemas and tree automata for unranked trees, Four one-shot learners for regular tree languages and their polynomial characterizability, Minimal consistent DFA from sample strings, Parameterized Weighted Containment, Learning Weighted Automata, Recent advances of grammatical inference, Minimisation of Multiplicity Tree Automata, Grammatical inference: An old and new paradigm, Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems withIDP3, Welfare maximization with friends-of-friends network externalities, On the complexity of automatic complexity, Polynomial inference of universal automata from membership and equivalence queries, Map learning with uninterpreted sensors and effectors, Efficiently identifying deterministic real-time automata from labeled data, Unnamed Item, Finding patterns common to a set of strings, On the Inference of Finite State Automata from Positive and Negative Data, Learning Tree Languages, Concurrent Kleene algebra with observations: from hypotheses to completeness, Polynomial characteristic sets for \(DFA\) identification, Learning Meets Verification, On the complexity of simple arithmetic expressions, Recognizing malicious software behaviors with tree automata inference, Learning context-free grammars from structural data in polynomial time, Mining probabilistic automata: a statistical view of sequential pattern mining, Learning regular languages using RFSAs., Inference of \(\omega\)-languages from prefixes., Regular inference as vertex coloring, On the zero-inequivalence problem for loop programs, On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}, Inductive inference of context-free languages based on context-free expressions, Improving active Mealy machine learning for protocol conformance testing, Automated assumption generation for compositional verification, GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE, On the Computational Complexity of Linear Discrepancy, The complexity of properly learning simple concept classes, Identification of Petri nets from knowledge of their language, Inductive reasoning and Kolmogorov complexity, Kernel methods for learning languages, Universal automata and NFA learning, Polynomial Identification of $$\omega $$-Automata, Model identification of unobservable behavior of discrete event systems using Petri nets, A multi-parameter analysis of hard problems on deterministic finite automata, Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT, Learning context-free grammars using tabular representations, Inference of regular languages using state merging algorithms with search, Minimizing finite automata is computationally hard, PAC Learning under Helpful Distributions, Descriptional and computational complexity of finite automata -- a survey, The efficiency of identifying timed automata and the power of clocks, On Testing P Systems, FSM inference from long traces, Unnamed Item, Model-based learning of interaction strategies in multi-agent systems, Complexity results for generating subgraphs, A sufficient condition to polynomially compute a minimum separating DFA, Optimal state reductions of automata with partially specified behaviors, Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games, Learning Stochastic Logical Automaton, The power of random counterexamples, Descriptional and Computational Complexity of Finite Automata, One-Clock Deterministic Timed Automata Are Efficiently Identifiable in the Limit, Types of Trusted Information That Make DFA Identification with Correction Queries Feasible, Efficient learning algorithms yield circuit lower bounds, The Monotone Satisfiability Problem with Bounded Variable Appearances, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization, Using case-based reasoning approach to the support of ill-structured decisions, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Exact complexity of problems of incompletely specified automata, Prediction-preserving reducibility, A dichotomy in the complexity of consistent query answering for queries with two atoms, Inferring a tree from walks, Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference, Learning algorithms, Limitations of learning in automata-based systems, Induction and Exploitation of Subgoal Automata for Reinforcement Learning, Recognizing Generating Subgraphs Revisited, Complexity of barrier coverage with relocatable sensors in the plane, On the hardness of approximating the minimum consistent acyclic DFA and decision diagram., A Survey of Opponent Modeling in Adversarial Domains, Hitting all maximal independent sets of a bipartite graph, Towards a general theory of topological maps
