NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY (Q3395129): Difference between revisions

@@ Property / cites work @@
+Intersection and union of regular languages and state complexity
+Normal rank
@@ Property / cites work @@
+Partial orders on words, minimal elements of regular languages, and state complexity
+Normal rank
@@ Property / cites work @@
+State-complexity of finite-state devices, state compressibility and incompressibility
+Normal rank
@@ Property / cites work @@
+Finite automata and unary languages
@@ Property / cites work: Finite automata and unary languages / rank @@
+Normal rank
@@ Property / cites work @@
+Transition complexity of language operations
@@ Property / cites work: Transition complexity of language operations / rank @@
+Normal rank
@@ Property / cites work @@
+Magic numbers in the state hierarchy of finite automata
+Normal rank
@@ Property / cites work @@
+A lower bound technique for the size of nondeterministic finite automata
+Normal rank
@@ Property / cites work @@
+On the average state and transition complexity of finite languages
+Normal rank
@@ Property / cites work @@
+Computing<i>ϵ</i>-Free NFA from Regular Expressions in<i>O</i>(<i>n</i>log<sup>2</sup>(<i>n</i>)) Time
+Normal rank
@@ Property / cites work @@
+NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Comparing the size of NFAs with and without \(\epsilon\)-transitions
+Normal rank
@@ Property / cites work @@
+Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
+Normal rank
@@ Property / cites work @@
+Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
+Normal rank
@@ Property / cites work @@
+A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
+Normal rank
@@ Property / cites work @@
+Minimal NFA Problems are Hard
@@ Property / cites work: Minimal NFA Problems are Hard / rank @@
+Normal rank
@@ Property / cites work @@
+STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
+Normal rank
@@ Property / cites work @@
+State complexity of some operations on binary regular languages
+Normal rank
@@ Property / cites work @@
+State complexity of cyclic shift
@@ Property / cites work: State complexity of cyclic shift / rank @@
+Normal rank
@@ Property / cites work @@
+On the State Minimization of Nondeterministic Finite Automata
+Normal rank
@@ Property / cites work @@
+Succinct representation of regular languages by Boolean automata
+Normal rank
@@ Property / cites work @@
+A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
+Normal rank
@@ Property / cites work @@
+Minimizing finite automata is computationally hard
+Normal rank
@@ Property / cites work @@
+Complementing unary nondeterministic automata
@@ Property / cites work: Complementing unary nondeterministic automata / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Simulations between Unary Automata
@@ Property / cites work: Optimal Simulations between Unary Automata / rank @@
+Normal rank
@@ Property / cites work @@
+UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
+Normal rank
@@ Property / cites work @@
+On the state complexity of reversals of regular languages
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of sweeping automata
@@ Property / cites work: Lower bounds on the size of sweeping automata / rank @@
+Normal rank
@@ Property / cites work @@
+The state complexities of some basic operations on regular languages
+Normal rank