Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity (Q3602795): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-540-70844-5_1
+Normal rank
@@ Property / OpenAlex ID @@
+W1843639509
@@ Property / OpenAlex ID: W1843639509 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4465328
@@ Property / cites work: Q4465328 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4474143
@@ Property / cites work: Q4474143 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4139689
@@ Property / cites work: Q4139689 / rank @@
+Normal rank
@@ 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 @@
+The Tractability Frontier for NFA Minimization
@@ Property / cites work: The Tractability Frontier for NFA Minimization / rank @@
+Normal rank
@@ Property / cites work @@
+Q4474150
@@ Property / cites work: Q4474150 / rank @@
+Normal rank
@@ Property / cites work @@
+Finite automata and unary languages
@@ Property / cites work: Finite automata and unary languages / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for the Transition Complexity of NFAs
+Normal rank
@@ Property / cites work @@
+Transition complexity of language operations
@@ Property / cites work: Transition complexity of language operations / rank @@
+Normal rank
@@ Property / cites work @@
+State complexity of power
@@ Property / cites work: State complexity of power / 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 @@
+Q5422234
@@ Property / cites work: Q5422234 / rank @@
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2003
@@ Property / cites work: Mathematical Foundations of Computer Science 2003 / rank @@
+Normal rank
@@ Property / cites work @@
+STACS 2005
@@ Property / cites work: STACS 2005 / 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 @@
+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 @@
+State Complexity of Union and Intersection of Finite Languages
+Normal rank
@@ Property / cites work @@
+Q5576262
@@ Property / cites work: Q5576262 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4531373
@@ Property / cites work: Q4531373 / rank @@
+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 @@
+Q4337605
@@ Property / cites work: Q4337605 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4465337
@@ Property / cites work: Q4465337 / rank @@
+Normal rank
@@ Property / cites work @@
+Communication complexity method for measuring nondeterminism in finite automata
+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 @@
+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 @@
+STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
+Normal rank
@@ Property / cites work @@
+Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet
+Normal rank
@@ Property / cites work @@
+Q4779161
@@ Property / cites work: Q4779161 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4453205
@@ Property / cites work: Q4453205 / rank @@
+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 @@
+Mathematical Foundations of Computer Science 2005
@@ Property / cites work: Mathematical Foundations of Computer Science 2005 / rank @@
+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 @@
+On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
+Normal rank
@@ Property / cites work @@
+Q4941905
@@ Property / cites work: Q4941905 / rank @@
+Normal rank
@@ Property / cites work @@
+UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
+Normal rank
@@ Property / cites work @@
+Q4991691
@@ Property / cites work: Q4991691 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+Normal rank
@@ Property / cites work @@
+On the state complexity of reversals of regular languages
+Normal rank
@@ Property / cites work @@
+Q4390537
@@ Property / cites work: Q4390537 / rank @@
+Normal rank
@@ Property / cites work @@
+Regular Expressions and NFAs Without ε-Transitions
+Normal rank
@@ Property / cites work @@
+Q5541340
@@ Property / cites work: Q5541340 / rank @@
+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 @@
+Q4131648
@@ Property / cites work: Q4131648 / rank @@
+Normal rank
@@ Property / cites work @@
+On Transition Minimality of Bideterministic Automata
+Normal rank
@@ Property / cites work @@
+Q2731279
@@ Property / cites work: Q2731279 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3152811
@@ Property / cites work: Q3152811 / rank @@
+Normal rank
@@ Property / cites work @@
+The state complexities of some basic operations on regular languages
+Normal rank