Learning from positive and negative examples: dichotomies and parameterized algorithms

DOI10.1007/978-3-031-06678-8_29OpenAlexW4285300288MaRDI QIDQ2169975

Mateus de Oliveira Oliveira, Petra Wolf, Jonas Lingg

Publication date: 30 August 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-06678-8_29

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Algorithms for learning regular expressions from positive data
• Languages of R-trivial monoids
• Optimization technique based on learning automata
• Learning automata and stochastic optimization
• Which problems have strongly exponential complexity?
• Recent advances in learning automata
• Problems on finite automata and the exponential time hypothesis
• Learning deterministic probabilistic automata from a model checking perspective
• Using forward reachability analysis for verification of lossy channel systems
• A multi-parameter analysis of hard problems on deterministic finite automata
• On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Supervisory Control of a Class of Discrete Event Processes
• Inference of Reversible Languages
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Complexity of automaton identification from given data
• On the complexity of minimum inference of regular sets
• Alternative Automata Characterization of Piecewise Testable Languages
• On finite monoids having only trivial subgroups
• The complexity of satisfiability problems
• Parameterized Algorithms
• Permutation automata
• Language identification in the limit
• Synchronization problems in automata without non-trivial cycles
• On the complexity of \(k\)-SAT
• Learning DFA from simple examples

This page was built for publication: Learning from positive and negative examples: dichotomies and parameterized algorithms