tree_automata/alternating/
mod.rs

1use std::collections::{HashMap, HashSet};
2use crate::{Symbol, Label, State};
3use crate::bottom_up;
4
5/// The empty conjunction is True.
6pub type Conjuction<Q, I> = Vec<(I, Q)>;
7
8/// The empty clause is False.
9pub type Clause<Q, I> = Vec<Conjuction<Q, I>>;
10
11/// Alternating tree automaton.
12pub struct Automaton<F: Symbol, Q: State, I> {
13    dummy_clauses: HashMap<F, Clause<Q, I>>,
14
15    /// Initial states.
16    initial_states: HashSet<Q>,
17
18    /// Internal structure of the automaton.
19    state_clauses: HashMap<Q, HashMap<F, Clause<Q, I>>>
20}
21
22impl<F: Symbol, Q: State, I> Automaton<F, Q, I> {
23    /// Create a new empty alternating tree automaton.
24    pub fn new() -> Automaton<F, Q, I> {
25        Automaton {
26            dummy_clauses: HashMap::new(),
27            initial_states: HashSet::new(),
28            state_clauses: HashMap::new()
29        }
30    }
31
32    pub fn states(&self) -> std::collections::hash_map::Keys<Q, HashMap<F, Clause<Q, I>>> {
33        self.state_clauses.keys()
34    }
35
36    pub fn clauses_for_state(&self, q: &Q) -> std::collections::hash_map::Iter<F, Clause<Q, I>> {
37        match self.state_clauses.get(q) {
38            Some(clauses) => clauses.iter(),
39            None => self.dummy_clauses.iter()
40        }
41    }
42
43    /// Add the given conjuction to the clause (state, symbol).
44    pub fn add(&mut self, state: &Q, symbol: &F, conjuction: Conjuction<Q, I>) {
45        match self.state_clauses.get_mut(state) {
46            Some(ref mut symbol_clauses) => {
47                match symbol_clauses.get_mut(symbol) {
48                    Some(ref mut clause) => {
49                        clause.push(conjuction);
50                    },
51                    None => {
52                        let clause = vec![conjuction];
53                        symbol_clauses.insert(symbol.clone(), clause);
54                    }
55                }
56            },
57            None => {
58                let mut symbol_clauses = HashMap::new();
59                let clause = vec![conjuction];
60                symbol_clauses.insert(symbol.clone(), clause);
61                self.state_clauses.insert(state.clone(), symbol_clauses);
62            }
63        }
64    }
65
66    pub fn is_initial(&self, q: &Q) -> bool {
67        self.initial_states.contains(q)
68    }
69
70    /// Set the given state an initial state.
71    /// Return `true` if the state was not already initial.
72    /// Return `false` if it was already an initial state.
73    pub fn set_initial(&mut self, q: Q) -> bool {
74        self.initial_states.insert(q)
75    }
76
77    pub fn map_states<R: State, M>(&self, g: M) -> Automaton<F, R, I> where M: Fn(&Q) -> R, I: Clone {
78        let mut mapped = Automaton::new();
79
80        for (state, clauses) in self.state_clauses.iter() {
81            let state = g(state);
82
83            for (f, clause) in clauses.iter() {
84                for conjunction in clause.iter() {
85                    let mapped_conjunction = conjunction.iter().map(|(index, q)| {
86                        (index.clone(), g(q))
87                    }).collect();
88
89                    mapped.add(&state, f, mapped_conjunction);
90                }
91            }
92        }
93
94        for q in self.initial_states.iter() {
95            mapped.set_initial(g(q));
96        }
97
98        mapped
99    }
100}
101
102impl<F: Symbol, Q: State> Automaton<F, Q, u32> {
103    /// Add a bottom-up transition.
104    /// It is added as a clause to the corresponding (state, symbol) pair.
105    pub fn add_transition(&mut self, bottom_up::Configuration(f, states): &bottom_up::Configuration<F, Q>, state: &Q) {
106        let conjunction = states.iter().enumerate().map(|(i, q)| (i as u32, q.clone())).collect();
107        self.add(state, f, conjunction)
108    }
109}
110
111impl<'a, F: Symbol, Q: State, L: Label> From<&'a bottom_up::Automaton<F, Q, L>> for Automaton<F, Q, u32> {
112    fn from(bottom_up: &'a bottom_up::Automaton<F, Q, L>) -> Automaton<F, Q, u32> {
113        let mut alternating = Automaton::new();
114
115        // add all transitions.
116        for (conf, _, q) in bottom_up.transitions() {
117            alternating.add_transition(conf, q)
118        }
119
120        // set intial states.
121        for q in bottom_up.final_states() {
122            alternating.set_initial(q.clone());
123        }
124
125        alternating
126    }
127}
tree_automata/alternating/mod.rs

tree_automata/alternating/
mod.rs
