#automata #dfa

l1-dfa

Deterministic Finite-State Automata Library for Rust, written in L1

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

MIT license

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