Paper Info
Title
Comparing Consecutive Letter Counts In Multiple Context-Free Languages
Abstract
Context-free grammars are not able to capture cross-serial dependencies occurring in some natural languages. To overcome this issue, Seki et al. introduced a generalization called m-multiple context-free grammars (m-MCFGs), which deal with m-tuples of strings. We show that m-MCFGs are capable of comparing the number of consecutive occurrences of at most 2m different letters. In particular, the language {a(1)(n1)a(2)(n2) ... a(2m+1)(n2m+1) vertical bar n(1) >= n(2) >= ... >= n(2m+1) >= 0} is (m + 1)-multiple context-free, but not m-multiple context-free. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.03.034
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Formal language, Multiple context free language
Journal
868
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Florian Lehner1217.24
Lindorfer Christian200.34