Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference

DOI10.3233/FI-2021-2004zbMath1482.68114MaRDI QIDQ4989176

Wojciech Wieczorek, Tomasz Jastrzab, Zbigniew J. Czech

Publication date: 21 May 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmssatisfiability problemconstraint satisfaction problemgrammatical inferencenondeterministic finite automatalearning regular languages

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal automata and NFA learning
• Characteristic sets for polynomial grammatical inference
• Learning regular languages using RFSAs.
• Principles of Constraint Programming
• Learning Regular Languages Using Nondeterministic Finite Automata
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Complexity of automaton identification from given data
• Minimal NFA Problems are Hard
• Applying Modern SAT-solvers to Solving Hard Problems
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Grammatical Inference: Algorithms and Applications
• On the Synthesis of Finite-State Machines from Samples of Their Behavior
• Language identification in the limit
• A Family of Algorithms for Non Deterministic Regular Languages Inference

This page was built for publication: Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference