Efficient testing and matching of deterministic regular expressions
From MaRDI portal
Publication:2402370
DOI10.1016/j.jcss.2017.05.013zbMath1372.68157OpenAlexW2604580999MaRDI QIDQ2402370
Publication date: 7 September 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://www.pure.ed.ac.uk/ws/files/32885322/jcss2017_3.pdf
deterministic regular expressionmatching time complexitynumerical occurrence indicatorstesting determinism
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding determinism of regular languages
- Deciding determinism of unary languages
- Preserving order in a forest in less than logarithmic time and linear space
- Regular expressions into finite automata
- From regular expressions to DFA's using compressed NFA's
- Checking determinism of regular expressions with counting
- One-unambiguity of regular expressions with numeric occurrence indicators
- On the computational power of pushdown automata
- Validating XML documents in the streaming model with external memory
- Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
- THE ABSTRACT THEORY OF AUTOMATA
- Fast Algorithms for Finding Nearest Common Ancestors
- Design and implementation of an efficient priority queue
- Fast text searching for regular expressions or automaton searching on tries
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Deciding Definability by Deterministic Regular Expressions
- XPath evaluation in linear time
- Regular Expressions and NFAs Without ε-Transitions
- Programming Techniques: Regular expression search algorithm
- Lowest common ancestors in trees and directed acyclic graphs
- Regular Expressions with Counting: Weak versus Strong Determinism
- One-unambiguous regular languages
