Struct TreeAutomaton 

pub struct TreeAutomaton {
    pub num_states: usize,
    pub final_states: HashSet<usize>,
    pub transitions: HashMap<(String, Vec<usize>), HashSet<usize>>,
}

A (bottom-up) tree automaton for recognizing regular tree languages.

States are usize indices. Transitions are of the form f(q_1, …, q_n) → q meaning: if children of f are in states q_1, …, q_n then f(…) can be assigned state q.

Fields

num_states: usize

Number of states.

final_states: HashSet<usize>

Set of accepting (final) states.

transitions: HashMap<(String, Vec<usize>), HashSet<usize>>

Transitions: maps (symbol, child_states) to a set of target states.

Implementations

impl TreeAutomaton

pub fn new(num_states: usize) -> Self

Create an automaton with num_states states.

pub fn add_final(&mut self, q: usize)

Mark state q as a final (accepting) state.

pub fn add_transition( &mut self, symbol: impl Into<String>, child_states: Vec<usize>, target: usize, )

Add a transition: when f is applied to children in states child_states, allow reaching state target.

pub fn run(&self, t: &Term) -> HashSet<usize>

Run the automaton bottom-up on term t.

Returns the set of states reachable at the root.

pub fn accepts(&self, t: &Term) -> bool

Check whether term t is accepted (root reachable in a final state).

pub fn is_empty(&self) -> bool

Returns true if the language is empty (no ground term is accepted).

This is a simple fixpoint check: compute the set of states reachable by any ground term, then check if any final state is reachable.

Trait Implementations

impl Clone for TreeAutomaton

fn clone(&self) -> TreeAutomaton

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TreeAutomaton

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.