proj-oot-ootPatternNotes1

Graph regexes should allow, at each step, any program without backwards jumps (this is similar to just allowing expressions, except that we also allow variable assignments to allow us to reuse results between steps of the subprogram).

also, remember to generalize linear regular expressions by (at least) having multiple 'directions' at each step (by directions, i don't really mean a lattice, i just mean that node in the graph might have more than 2 edges, and the topology of the entire graph may not be linear).

---

also consider relational data queries.

what's the time complexity of relational data queries?

they are not Turing-complete [1] (but some common extensions are [2])

and queries are NP-hard in one model but not in another [3] [4]

comparison of complexity to regular expressions?

---

" Richer patterns

Another small, tasty question: what's the most complicated pattern you can write in a match expression in your language? We have plenty of automata theory for compiling-down all sorts of complicated patterns to efficient matchers, and we have tons of evidence that users enjoy writing pattern-based programs, that users write shorter, simpler and less failure-prone programs when they can express a task in pattern/action form, and that pattern-sets are amenable to extremely helpful static analysis / diagnosis along the lines of exhaustiveness checking, equivalence checking, emptiness checking and so forth. So why not push the patterns in your language to the limit?

I think this is a very fruitful area to explore, especially building out from tree-patterns and visibly-pushdown patterns. Some languages make the pattern system extensible, eg. F# active patterns at the cost of formal reasoning about it at compile time; others push a specific extended pattern-automaton theory into the type system. Many languages in this space, eg. CDuce or FAST, are (unfortunately) "XML oriented" which turns people off the technology lately, since XML is out of fashion, but they're worth looking into! " [5]

---