On the complexity of a mildly context-sensitive language class

Abstract

We study the mildly context-sensitive class of languages generated by controlled linear grammars with context-free (exact) control, or equivalently, accepted by a family of two-head pushdown automata and a family of input reversal pushdown automata. (A controlled grammar is with exact control, if there exists a valid derivation in the grammar for each word of the control language. A pushdown automaton is input reversal, if it is able to reverse the yet unread part of its input word.) We present a simple normal form for linear grammars with context-free exact control, and study the problem of parsing the generated languages. We give a new parsing algorithm based on Earley’s method having a time complexity of O(n5). © Institut für Informatik · Justus-Liebig-Universität Giessen.