A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
From MaRDI portal
Publication:1007546
DOI10.1016/S0020-0190(02)00436-2zbMath1173.68555MaRDI QIDQ1007546
Publication date: 23 March 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items
Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ PATH-EQUIVALENT DEVELOPMENTS IN ACYCLIC WEIGHTED AUTOMATA ⋮ A faster algorithm for finding shortest substring matches of a regular expression ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Transition complexity of language operations ⋮ Lower bounds for the transition complexity of NFAs ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Conversion of regular expressions into realtime automata
Cites Work
