The tractability frontier for NFA minimization (Q414869): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2011.03.001
+Normal rank
@@ Property / OpenAlex ID @@
+W2157017998
@@ Property / OpenAlex ID: W2157017998 / rank @@
+Normal rank
@@ Property / cites work @@
+Implementation and Application of Automata
@@ Property / cites work: Implementation and Application of Automata / rank @@
+Normal rank
@@ Property / cites work @@
+Hyper-minimizing minimized deterministic finite state automata
+Normal rank
@@ Property / cites work @@
+Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
+Normal rank
@@ Property / cites work @@
+The Tractability Frontier for NFA Minimization
@@ Property / cites work: The Tractability Frontier for NFA Minimization / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Hyper-minimisation Made Efficient
@@ Property / cites work: Hyper-minimisation Made Efficient / rank @@
+Normal rank
@@ Property / cites work @@
+Succinctness of regular expressions with interleaving, intersection and counting
+Normal rank
@@ Property / cites work @@
+Regular Expressions with Counting: Weak versus Strong Determinism
+Normal rank
@@ Property / cites work @@
+Q4910730
@@ Property / cites work: Q4910730 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5422234
@@ Property / cites work: Q5422234 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing nfa's and regular expressions
@@ Property / cites work: Minimizing nfa's and regular expressions / rank @@
+Normal rank
@@ Property / cites work @@
+Finding Lower Bounds for Nondeterministic State Complexity Is Hard
+Normal rank
@@ Property / cites work @@
+Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
+Normal rank
@@ Property / cites work @@
+Tight Bounds on the Descriptional Complexity of Regular Expressions
+Normal rank
@@ Property / cites work @@
+Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
+Normal rank
@@ Property / cites work @@
+An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
+Normal rank
@@ Property / cites work @@
+Q4531373
@@ Property / cites work: Q4531373 / rank @@
+Normal rank
@@ Property / cites work @@
+Regular Expressions with Numerical Constraints and Automata with Counters
+Normal rank
@@ Property / cites work @@
+Q2754144
@@ Property / cites work: Q2754144 / rank @@
+Normal rank
@@ Property / cites work @@
+Comparing the size of NFAs with and without \(\epsilon\)-transitions
+Normal rank
@@ Property / cites work @@
+THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
+Normal rank
@@ Property / cites work @@
+Minimal NFA Problems are Hard
@@ Property / cites work: Minimal NFA Problems are Hard / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing finite automata is computationally hard
+Normal rank
@@ Property / cites work @@
+Unambiguous Finite Automata over a Unary Alphabet
@@ Property / cites work: Unambiguous Finite Automata over a Unary Alphabet / rank @@
+Normal rank
@@ Property / cites work @@
+Three Partition Refinement Algorithms
@@ Property / cites work: Three Partition Refinement Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Descriptional Complexity of Nondeterministic Finite Automata
+Normal rank
@@ Property / cites work @@
+Regular Expressions and NFAs Without ε-Transitions
+Normal rank
@@ Property / cites work @@
+On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
+Normal rank
@@ Property / cites work @@
+Q4131648
@@ Property / cites work: Q4131648 / rank @@
+Normal rank