Journal article

Publication year: 2007

Pages: 2152-2164

Journal: Discrete Applied Mathematics

Volume number: 155

Issue number: 16

ISSN: 0166-218X

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.dam.2007.05.021

Publisher: Elsevier

Abstract: 
Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time. 0 2007 Elsevier B.V. All rights reserved.

Harvard Citation style: Kutrib, M. and Malcher, A. (2007) Finite turns and the regular closure of linear context-free languages, Discrete Applied Mathematics, 155(16), pp. 2152-2164. https://doi.org/10.1016/j.dam.2007.05.021

APA Citation style: Kutrib, M., & Malcher, A. (2007). Finite turns and the regular closure of linear context-free languages. Discrete Applied Mathematics. 155(16), 2152-2164. https://doi.org/10.1016/j.dam.2007.05.021