Minimal NFA Problems are Hard
From MaRDI portal
Publication:4277533
DOI10.1137/0222067zbMath0799.68079OpenAlexW2040834199MaRDI QIDQ4277533
Publication date: 7 February 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222067
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (75)
Multiheuristic approach to discrete optimization problems ⋮ Compression of finite-state automata through failure transitions ⋮ Rewriting regular inequalities ⋮ Minimizing nfa's and regular expressions ⋮ Unnamed Item ⋮ On size reduction techniques for multitape automata ⋮ On the complexity of determinizing monitors ⋮ Obtaining shorter regular expressions from finite-state automata ⋮ Matrices of Bounded Psd Rank are Easy to Detect ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ On quotients of formal power series ⋮ Unnamed Item ⋮ Minimisation of Multiplicity Tree Automata ⋮ Alternating sign matrices, related (0,1)-matrices, and the Smith normal form ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions ⋮ Boundary sets of regular and context-free languages ⋮ Simulation relations and applications in formal methods ⋮ Left is Better Than Right for Reducing Nondeterminism of NFAs ⋮ The tractability frontier for NFA minimization ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Minimization of automata for liveness languages ⋮ Complexity of exclusive nondeterministic finite automata ⋮ On the computational complexity of problems related to distinguishability sets ⋮ An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ ON TRANSITION MINIMALITY OF BIDETERMINISTIC AUTOMATA ⋮ Distributed XML design ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ Nondeterministic syntactic complexity ⋮ On Language Decompositions and Primality ⋮ A lower bound technique for the size of nondeterministic finite automata ⋮ Succinct description of regular languages by weak restarting automata ⋮ ENUMERATING NONDETERMINISTIC AUTOMATA FOR A GIVEN LANGUAGE WITHOUT CONSTRUCTING THE CANONICAL AUTOMATON ⋮ Further improvements of determinization methods for fuzzy finite automata ⋮ Lower bounds for the transition complexity of NFAs ⋮ A search algorithm for subshift attractors of cellular automata ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ Some results on the structure of unary unambiguous automata ⋮ 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 ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ The efficiency of identifying timed automata and the power of clocks ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Fuzzy relation equations and reduction of fuzzy automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Unnamed Item ⋮ Boosting over non-deterministic ZDDs ⋮ Reduction of fuzzy automata by means of fuzzy quasi-orders ⋮ Optimal state reductions of automata with partially specified behaviors ⋮ Unnamed Item ⋮ A theory of ultimately periodic languages and automata with an application to time granularity ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Factoring a band matrix over a semiring ⋮ Determinizing monitors for HML with recursion ⋮ Better Hyper-minimization ⋮ Covering graphs with few complete bipartite subgraphs ⋮ 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 ⋮ Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs ⋮ Minimizing GFG Transition-Based Automata ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference ⋮ Minimisation of automata ⋮ Deterministic generalized automata ⋮ Efficient implementation of regular languages using reversed alternating finite automata ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Note on the complexity of Las Vegas automata problems ⋮ Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997 ⋮ The binary rank of circulant block matrices ⋮ Learning residual alternating automata ⋮ More on Minimizing Finite Automata with Errors — Nondeterministic Machines
This page was built for publication: Minimal NFA Problems are Hard
