Comparing consecutive letter counts in multiple context-free languages

DOI10.1016/J.TCS.2021.03.034MaRDI QIDQ831122zbMATH OpenOpenAlexFDO

Authors Florian Lehner, Christian Lindorfer

Publication date 10 May 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.08236

zbMATH Keywords

formal languagemultiple context-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Abstract: Context-free grammars are not able to model cross-serial dependencies in 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^{n_1}{a}_2^{n_2}dots{a}_k^{n_{2m+1}}mid{n}_{1}geq{n}_{2}geqdotsgeq{n}_{2m+1}geq0$ is $(m+1)$-multiple context-free, but not $m$-multiple context-free.

Recommendations

• On lengths of words in context-free languages
• Context-Free Languages of Countable Words
• scientific article; zbMATH DE number 4033108
• Length considerations in context-free languages
• Counting \(l\)-letter subwords in compositions
• Counting subwords and regular languages
• Counting Finite Languages by Total Word Length
• The complexity of computing the number of strings of given length in context-free languages
• scientific article; zbMATH DE number 1261119
• scientific article; zbMATH DE number 1552330

Cites work

• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• On multiple context-free grammars
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• The failure of the strong pumping lemma for multiple context-free languages
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language

Cited in

(2)

• Self-avoiding walks and multiple context-free languages
• Counting Finite Languages by Total Word Length

This page was built for publication: Comparing consecutive letter counts in multiple context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831122)