It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for recognizing PMCFG languages? Judgjing from extended Chomsky hierarchy (https://en.wikipedia.org/wiki/Chomsky_hierarchy) such machine if between pushdown automaton (for CFG) and linear bounded Turing machine (for full context-sensitive grammars). But what machine exactly it is?
I have some hints that top-down resp bottom-up tree automata could be the answer, it is possible? Why tree?