Expression Tree Optimization

Investigate the applicability of tree/dag transducers to encode tree optimizations.

References/resources for tree/dag transducers:

• DAGGER: A Toolkit for Automata on Directed Acyclic Graphs - code available at link
• Kleen - github source
• TrUDucer - gitlab source
• FACTORIE - graphical modeling toolkit
• CDEC - github

Papers without code covering Tree Transducers:

• "Training Tree Transducers", Jonathan Graehl, Kevin Knight and Jonathan May. Computational Linguistics, 34(3), 2008.
• An overview of probabilistic tree transducers for natural language processing
• "Training tree transducers" part 1
• "Training tree transducers" part 2
• "Streaming tree transducers"
• "TTT: A tree transduction language for syntactic and semantic processing
• "FAST: A transducer-based language for tree manipulation" - microsoft reference
• "A tree transducer model for grammatical error correction"
• "Learning Interaction Dynamics with Coupled Hidden Markov Models"
• "Tree Transduction Tools for cdec"
• "cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models"

Explore the application of HMMs over expression trees.

Papers + code covering HMMs applied to trees:

• "NLTK HMM tutorial"
• "HMM tutorial, part 1"
• "HMM tutorial, part 2"
• "An Introduction to Hidden Markov Models and Bayesian Networks" - Specifically, Section 5.2, Extension 2: Tree Structured HMMs.
• "Hidden Markov Decision Trees"
• "Hidden Markov Tree Model for Word Alignment"
• "Tree Hidden Markov Model" - gitlab source code

Finite State Transducer software:

• RWTH FSA Toolkit
• OpenFST