summaryrefslogtreecommitdiff
path: root/chain/src
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src')
-rw-r--r--chain/src/plan.org28
1 files changed, 26 insertions, 2 deletions
diff --git a/chain/src/plan.org b/chain/src/plan.org
index 75acf30..bbd6683 100644
--- a/chain/src/plan.org
+++ b/chain/src/plan.org
@@ -38,11 +38,30 @@
finite automata.
* [X] Test the removal of dead states, where a state is dead if
and only if no other states have an edge into that state.
-- [-] Refactor [2/5]
+- [-] Refactor [2/8]
+ [X] Implement a data type for graphs with labels on vertices and
edges, but do not need to index edges by labels, which can index
vertices by labels instead.
+ * [X] Test it.
+ [X] Implement a builder that borrows a graph mutably.
+ * [X] Test it.
+ + [ ] Implement a data type for graphs in which every node knows its
+ parents, and every node has a unique label but edges have no
+ labels.
+ * [ ] Test it.
+ + [ ] We need to record the expansions of those "virtual nodes".
+ That is, the virtual nodes represent atomic languages such as
+ [s]^{(t)} where s is a non-terminal and t is a terminal. To be more
+ specific, it represents the derivative of the left-linear closure
+ of the non-terminal s with respect to the terminal t. The
+ left-linear closure of s is the set of all strings (consisting of
+ terminals and non-terminals alike) that are derivable from s
+ alone, without consuming any inputs, by expanding according to the
+ grammar rules. This means that we need to know which
+ non-terminals were expanded in order to get to a state in [s]^{(t)}.
+ + [ ] Each edge in the chain-rule machine needs to be labelled also
+ with a position in the forest. This perfectly solves the problem
+ of those "plugs"!
+ [ ] When we pull in some regular language because of the
left-linear expansion, we need to mark that branch as coming from
left-linear expansions. This is necessary because we cannot
@@ -66,7 +85,12 @@
+ [X] First define a trait with the expected behaviours.
+ [ ] Then implement them as doubly labelled graphs.
+ [ ] Thenimplement finding derivatives by use of the chain rule.
-- [-] Implement forests [1/2]
+- [-] Implement forests [2/3]
+ + [X] Design a format of forests. This should be the most crucial
+ thing to do, in order to have a better understanding of the whole
+ picture. I need to have a clear understanding of the details of
+ the binarised shared packed parsed forests, that reflects the
+ regular expressions in the grammar equations.
+ [X] Define a trait with the expected behaviours.
+ [-] Implement them using adjacency map: we only need one label per
edge, and we do not wish to exclude duplicate edges, and we do not