Parallel algorithms for minimal nondeterministic finite automata inference

DOI10.3233/FI-2021-2004MaRDI QIDQ4989176zbMATH OpenFDO

Authors Tomasz Jastrzab, Wojciech Wieczorek, Zbigniew J. Czech

Publication date 21 May 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2021-2004

zbMATH Keywords

constraint satisfaction problemgrammatical inferencelearning regular languagesnondeterministic finite automataparallel algorithmssatisfiability problem

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Recommendations

• Learning Regular Languages Using Nondeterministic Finite Automata
• A Family of Algorithms for Non Deterministic Regular Languages Inference
• scientific article; zbMATH DE number 1419219
• Efficient algorithms for the inference of minimum size DFAs
• Publication:4942035

Cites work

• A Family of Algorithms for Non Deterministic Regular Languages Inference
• Applying modern SAT-solvers to solving hard problems
• Characteristic sets for polynomial grammatical inference
• Complexity of automaton identification from given data
• Grammatical Inference: Algorithms and Applications
• Grammatical inference. Learning automata and grammars.
• scientific article; zbMATH DE number 58314 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 783783 (Why is no real title available?)
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Language identification in the limit
• Learning Regular Languages Using Nondeterministic Finite Automata
• Learning regular languages using RFSAs.
• Minimal NFA Problems are Hard
• On the Synthesis of Finite-State Machines from Samples of Their Behavior
• Principles of Constraint Programming
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Universal automata and NFA learning

Cited in

(9)

• Regular inference as vertex coloring
• Learning Regular Languages Using Nondeterministic Finite Automata
• On Parallel Implementations of Deterministic Finite Automata
• Parallel decision procedures for finite state automata
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• scientific article; zbMATH DE number 1419219 (Why is no real title available?)
• A Family of Algorithms for Non Deterministic Regular Languages Inference
• Report on the exact methods for finding minimum-sized DFA
• Universal automata and NFA learning

This page was built for publication: Parallel algorithms for minimal nondeterministic finite automata inference

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