A close analysis of the subset construction

DOI10.1007/978-3-031-97100-6_2MaRDI QIDQ6884670zbMATH OpenFDO

Authors Ivan Baburin, Ryan Cotterell

Publication date 15 December 2025

Full work available at URL https://doi.org/10.1007/978-3-031-97100-6_2

zbMATH Keywords

determinizationstate complexitysubset construction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Antichains: A New Algorithm for Checking Universality of Finite Automata
• Boolean-width of graphs
• Descriptional and computational complexity of finite automata -- a survey
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Determination of finite automata accepting subregular languages
• Efficient representation of perm groups
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• OpenFst: A General and Efficient Weighted Finite-State Transducer Library
• Relationships between nondeterministic and deterministic tape complexities
• Subset construction complexity for homogeneous automata, position automata and ZPC-structures
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The parallel complexity of finite-state automata problems
• Theory of átomata

This page was built for publication: A close analysis of the subset construction

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