Complexity of automaton identification from given data

Cited in

(only showing first 100 items - show all)

Inferring a tree from walks
Learning communicating state machines
Efficient learning of typical finite automata from random walks
LARS: a learning algorithm for rewriting systems
Towards a general theory of topological maps
Four one-shot learners for regular tree languages and their polynomial characterizability
Recognizing generating subgraphs revisited
Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3
A survey of opponent modeling in adversarial domains
Complexity of barrier coverage with relocatable sensors in the plane
Prediction-preserving reducibility
On Testing P Systems
Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
Identification of Petri nets from knowledge of their language
Tree containment with soft polytomies
Inductive inference of ultimately periodic sequences
Map learning with uninterpreted sensors and effectors
Approximate learning of limit-average automata
Analyzing robustness of Angluin's \(L^*\) algorithm in presence of noise
Learning context-free grammars using tabular representations
Model identification of unobservable behavior of discrete event systems using Petri nets
Parameterized weighted containment
Efficiently identifying deterministic real-time automata from labeled data
Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT
Learning regular languages using RFSAs.
Using case-based reasoning approach to the support of ill-structured decisions
The efficiency of identifying timed automata and the power of clocks
Inductive inference of context-free languages based on context-free expressions
Learning Meets Verification
Automated assumption generation for compositional verification
Recognizing malicious software behaviors with tree automata inference
Minimizing finite automata is computationally hard
Joint learning of reward machines and policies in environments with partially known semantics
Learning regular sets from queries and counterexamples
A dichotomy in the complexity of consistent query answering for queries with two atoms
Exact complexity of problems of incompletely specified automata
On the Computational Complexity of Linear Discrepancy
On the minimization of XML schemas and tree automata for unranked trees
PAC learning under helpful distributions
Constructing deterministic parity automata from positive and negative examples
Mining probabilistic automata: a statistical view of sequential pattern mining
Complexity results for generating subgraphs
Passive automata learning: DFAs and NFAs
Finding patterns common to a set of strings
FSM inference from long traces
Universal automata and NFA learning
Polynomial characteristic sets for \(DFA\) identification
Minimal consistent DFA revisited
Optimal state reductions of automata with partially specified behaviors
Graph orientation to maximize the minimum weighted outdegree
On the hardness of approximating the minimum consistent OBDD problem
Concurrent Kleene algebra with observations: from hypotheses to completeness
Bounded degree graph inference from walks
Inferring a tree from walks
Certifying DFA bounds for recognition and separation
Learning context-free grammars from structural data in polynomial time
scientific article; zbMATH DE number 7561484 (Why is no real title available?)
Descriptional and Computational Complexity of Finite Automata
Regular inference as vertex coloring
A sufficient condition to polynomially compute a minimum separating DFA
Learning weighted automata
On simplified NP-complete variants of \textsc{Monotone 3-Sat}
On the complexity of simple arithmetic expressions
Induction and exploitation of subgoal automata for reinforcement learning
Learning from positive and negative examples: new proof for binary alphabets
Model-based learning of interaction strategies in multi-agent systems
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
Polynomial inference of universal automata from membership and equivalence queries
On the Inference of Finite State Automata from Positive and Negative Data
On the zero-inequivalence problem for loop programs
Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas
Recent advances of grammatical inference
Improving active Mealy machine learning for protocol conformance testing
Hardness of approximate two-level logic minimization and PAC learning with membership queries
Welfare maximization with friends-of-friends network externalities
Kernel methods for learning languages
Inference of regular languages using state merging algorithms with search
Circuit lower bounds from learning-theoretic approaches
Learning Tree Languages
A multi-parameter analysis of hard problems on deterministic finite automata
Inductive reasoning and Kolmogorov complexity
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Limitations of learning in automata-based systems
Active learning for sound negotiations
Grammatical inference: An old and new paradigm
Learning reward machines: a study in partially observable reinforcement learning
Descriptional and computational complexity of finite automata -- a survey
The power of random counterexamples
Analyzing robustness of Angluin's \(\mathrm{L}^\ast\) algorithm in presence of noise
Inference of -languages from prefixes.
Controlling entity integrity with key sets
The complexity of properly learning simple concept classes
Minimal consistent DFA from sample strings
Learning algorithms
Learning Stochastic Logical Automaton
Identification of pattern languages from examples and queries
Parallel algorithms for minimal nondeterministic finite automata inference
Polynomial identification of \(\omega \)-automata
On the complexity of automatic complexity
Learning from positive and negative examples: dichotomies and parameterized algorithms

This page was built for publication: Complexity of automaton identification from given data

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