Complexity of automaton identification from given data

Cited in

(only showing first 100 items - show all)

Limitations of learning in automata-based systems
Identification of pattern languages from examples and queries
Learning regular sets from queries and counterexamples
Inductive inference of ultimately periodic sequences
Finding patterns common to a set of strings
On the complexity of simple arithmetic expressions
On the zero-inequivalence problem for loop programs
Inductive reasoning and Kolmogorov complexity
Using case-based reasoning approach to the support of ill-structured decisions
Bounded degree graph inference from walks
Inferring a tree from walks
Efficient learning of typical finite automata from random walks
Recent advances of grammatical inference
Map learning with uninterpreted sensors and effectors
Learning regular languages using RFSAs.
Inference of -languages from prefixes.
Autonomous agents modelling other agents: a comprehensive survey and open problems
Inferring regular languages and \(\omega\)-languages
Welfare maximization with friends-of-friends network externalities
On the complexity of automatic complexity
Exact complexity of problems of incompletely specified automata
Mining probabilistic automata: a statistical view of sequential pattern mining
Model identification of unobservable behavior of discrete event systems using Petri nets
Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT
FSM inference from long traces
Learning algorithms
Certifying DFA bounds for recognition and separation
Learning from positive and negative examples: dichotomies and parameterized algorithms
Minimal consistent DFA from sample strings
Concurrent Kleene algebra with observations: from hypotheses to completeness
On simplified NP-complete variants of \textsc{Monotone 3-Sat}
A multi-parameter analysis of hard problems on deterministic finite automata
A sufficient condition to polynomially compute a minimum separating DFA
Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
The power of random counterexamples
Complexity of barrier coverage with relocatable sensors in the plane
Hitting all maximal independent sets of a bipartite graph
LARS: a learning algorithm for rewriting systems
Recognizing malicious software behaviors with tree automata inference
The complexity of properly learning simple concept classes
Identification of Petri nets from knowledge of their language
Learning context-free grammars using tabular representations
Inference of regular languages using state merging algorithms with search
Efficient learning algorithms yield circuit lower bounds
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
Circuit lower bounds from learning-theoretic approaches
PAC learning under helpful distributions
Parameterized weighted containment
Learning weighted automata
On the Inference of Finite State Automata from Positive and Negative Data
Learning Tree Languages
Graph orientation to maximize the minimum weighted outdegree
Minimal consistent DFA revisited
Types of trusted information that make DFA identification with correction queries feasible
Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Learning Meets Verification
Learning Stochastic Logical Automaton
Descriptional and Computational Complexity of Finite Automata
One-Clock Deterministic Timed Automata Are Efficiently Identifiable in the Limit
Inductive inference of context-free languages based on context-free expressions
Four one-shot learners for regular tree languages and their polynomial characterizability
Efficiently identifying deterministic real-time automata from labeled data
Polynomial characteristic sets for \(DFA\) identification
Model-based learning of interaction strategies in multi-agent systems
Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3
Regular inference as vertex coloring
Improving active Mealy machine learning for protocol conformance testing
The Monotone Satisfiability Problem with Bounded Variable Appearances
Parallel algorithms for minimal nondeterministic finite automata inference
A survey of opponent modeling in adversarial domains
On the hardness of approximating the minimum consistent OBDD problem
Tree containment with soft polytomies
Learning definable hypotheses on trees
Inferring a tree from walks
Polynomial identification of \(\omega \)-automata
On Testing P Systems
Descriptional and computational complexity of finite automata -- a survey
The efficiency of identifying timed automata and the power of clocks
Induction and exploitation of subgoal automata for reinforcement learning
Recognizing generating subgraphs revisited
On the Computational Complexity of Linear Discrepancy
Approximate learning of limit-average automata
Learning of Structurally Unambiguous Probabilistic Grammars
Hardness of approximate two-level logic minimization and PAC learning with membership queries
Grammatical inference: An old and new paradigm
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
Analyzing robustness of Angluin's \(\mathrm{L}^\ast\) algorithm in presence of noise
Learning communicating state machines
Analyzing robustness of Angluin's L^* algorithm in presence of noise
Joint learning of reward machines and policies in environments with partially known semantics
Constructing deterministic parity automata from positive and negative examples
Active learning for sound negotiations
Using finite automata to compute the base-b representation of the golden ratio and other quadratic irrationals
Computing the base-\(b\) representation of quadratic irrationals using automata
A framework for computing upper bounds in passive learning settings

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)