Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata

From MaRDI portal
Publication:5946055

DOI10.1006/jcss.2001.1748zbMath1014.68093OpenAlexW2039984653MaRDI QIDQ5946055

Juraj Hromkovič, Thomas Wilke, Sebastian Seibert

Publication date: 2 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/167283803961a7216e349d27bcbfb4ee377393c8




Related Items (29)

Comparing the size of NFAs with and without \(\epsilon\)-transitionsDeciding determinism of caterpillar expressionsTHE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONSPassive testing with asynchronous communications and timestampsSeries parallel digraphs with loopsDeterministic Caterpillar ExpressionsTranslation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitionsEfficient weighted expressions conversionA faster algorithm for finding shortest substring matches of a regular expressionOn the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their SizesConstruction of Tree Automata from Regular ExpressionsFollow automata.Reducing NFAs by invariant equivalences.Postfix automataA FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONSRegular Language Constrained Sequence Alignment RevisitedTransition complexity of language operationsLower bounds for the transition complexity of NFAsOn the complexity of decidable cases of the commutation problem of languagesA New Family of Regular Operators Fitting with the Position Automaton ComputationNondeterministic Finite Automata—Recent Results on the Descriptional and Computational ComplexityFrom Finite Automata to Regular Expressions and Back — A Summary on Descriptional ComplexityMulti-tilde Operators and Their Glushkov AutomataPractical regular expression constrained sequence alignmentConstruction of tree automata from regular expressionsNONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITYDescriptional complexity of regular languagesConversion of regular expressions into realtime automataThe Bottom-Up Position Tree Automaton and the Father Automaton



Cites Work


This page was built for publication: Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata