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?


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.