Minimal NFA Problems are Hard
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 176769
- The parallel complexity of finite-state automata problems
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- scientific article; zbMATH DE number 2040922
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
Cited in
(only showing first 100 items - show all)- Covering graphs with few complete bipartite subgraphs
- On NFAs where all states are final, initial, or both
- The parallel complexity of finite-state automata problems
- Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
- Deterministic generalized automata
- Efficient implementation of regular languages using reversed alternating finite automata
- Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997
- Descriptional and computational complexity of the circuit representation of finite automata
- Problems on finite automata and the exponential time hypothesis
- On the computational complexity of problems related to distinguishability sets
- Mergible states in large NFA
- An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
- Factoring a band matrix over a semiring
- Minimisation of automata
- The binary rank of circulant block matrices
- Learning residual alternating automata
- Nondeterministic syntactic complexity
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Determinizing monitors for HML with recursion
- Multiheuristic approach to discrete optimization problems
- On the complexity of determinizing monitors
- Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
- Minimizing nfa's and regular expressions
- On quotients of formal power series
- Problems on finite automata and the exponential time hypothesis
- Compressed membership for NFA (DFA) with compressed labels is in NP (P)
- Compression of finite-state automata through failure transitions
- On language decompositions and primality
- Better hyper-minimization. Not as fast, but fewer errors
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Note on the complexity of Las Vegas automata problems
- Remarks on multiple entry deterministic finite automata
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- ON TRANSITION MINIMALITY OF BIDETERMINISTIC AUTOMATA
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Descriptional and Computational Complexity of Finite Automata
- An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
- Compact Normal Form for Regular Languages as Xor Automata
- Implementation of State Elimination Using Heuristics
- scientific article; zbMATH DE number 4061217 (Why is no real title available?)
- scientific article; zbMATH DE number 4080912 (Why is no real title available?)
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- scientific article; zbMATH DE number 176769 (Why is no real title available?)
- The tractability frontier for NFA minimization
- Extremal minimality conditions on automata
- scientific article; zbMATH DE number 2040922 (Why is no real title available?)
- scientific article; zbMATH DE number 2081039 (Why is no real title available?)
- Matrices of bounded psd rank are easy to detect
- The nonnegative rank of a matrix: hard problems, easy solutions
- Problems and invariants connected with bicliques and multicliques of graphs
- A multivariate analysis of some DFA problems
- Deciding determinism of regular languages
- scientific article; zbMATH DE number 1419219 (Why is no real title available?)
- Automata that may change their mind
- Parallel algorithms for minimal nondeterministic finite automata inference
- Rewriting regular inequalities
- Minimizing GFG Transition-Based Automata
- Optimal regular expressions for permutations
- Minimization and canonization of GFG transition-based automata
- Nondeterministic state complexity of proportional removals
- Optimal state reductions of automata with partially specified behaviors
- Never minimal automata and the rainbow bipartite subgraph problem
- More on Minimizing Finite Automata with Errors — Nondeterministic Machines
- Some results on the structure of unary unambiguous automata
- Nondeterministic tree width of regular languages
- Descriptional and computational complexity of finite automata -- a survey
- The efficiency of identifying timed automata and the power of clocks
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- ENUMERATING NONDETERMINISTIC AUTOMATA FOR A GIVEN LANGUAGE WITHOUT CONSTRUCTING THE CANONICAL AUTOMATON
- Boosting over non-deterministic ZDDs
- State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
- Simulation relations and applications in formal methods
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Minimization of automata for liveness languages
- Complexity of exclusive nondeterministic finite automata
- Distributed XML design
- Extended formulations via decision diagrams
- A lower bound technique for the size of nondeterministic finite automata
- Further improvements of determinization methods for fuzzy finite automata
- Minimising good-for-games automata is NP-complete
- A study of the binary and Boolean rank of matrices with small constant real rank
- Small balanced vertex separators in NFA to regular expression conversion
- The -rank of a (0, 1)-matrix
- Approximate state reduction of fuzzy finite automata
- K-balanced biclique partition: kernelization and efficient algorithms
- Complexity of exclusive nondeterministic finite automata
- Deterministic suffix-reading automata
- k-balanced biclique partition on signed bipartite graphs
- Incremental algorithms for solving regular expression intersection non-emptiness
- Weak minimization of DFA -- an algorithm and applications
- Bideterministic automata and minimal representations of regular languages
- NFA reduction algorithms by means of regular inequalities
- Minimizing finite automata is computationally hard
- A study of the binary and Boolean rank of matrices with small constant real rank
- Deterministic suffix-reading automata
- Reduction of fuzzy automata by means of fuzzy quasi-orders
- Optimal state reductions of automata with partially specified behaviors
- A theory of ultimately periodic languages and automata with an application to time granularity
- On size reduction techniques for multitape automata
- Obtaining shorter regular expressions from finite-state automata
This page was built for publication: Minimal NFA Problems are Hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4277533)
