12 releases
0.1.1 | Mar 2, 2023 |
---|---|
0.1.0 | Mar 1, 2023 |
0.0.10 | Mar 1, 2023 |
0.0.9 | Feb 28, 2023 |
#1554 in Math
9KB
163 lines
L1 DFA
Deterministic Finite-State Automata Library for Rust, written in L1.
Features
try_parse(regex)
- space complexity = $O(2^x)$
- time complexity = $O(2^x)$
- worst case example:
/(01|10)*[01]{x}/
x.accepts(s)
- time complexity = $s$
x.is_empty()
- time complexity = $x$
x.complement()
- space complexity = $x$
- time complexity = $x$
x.intersect(y)
- space complexity = $xy$
- time complexity = $xy$
x.union(y)
- space complexity = $xy$
- time complexity = $xy$
x.minimize()
- time complexity = $x\log x\Sigma_x$
x.is_subset_of(y)
- space complexity = $xy$
- time complexity = $xy$
x.reverse()
- space complexity = $O(2^x)$
- time complexity = $O(2^x)$
- worst case example:
/[01]{x}(01|10)*/
Dependencies
~1.5MB
~50K SLoC