0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.