Comparing consecutive letter counts in multiple context-free languages

Florian Lehner; Christian Lindorfer

doi:10.1016/j.tcs.2021.03.034

Comparing consecutive letter counts in multiple context-free languages

Florian Lehner^*, Christian Lindorfer

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Diskrete Mathematik (5050)

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

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 ₁ ^{n
₁}a ₂ ^{n
₂}⋯a _2m+1 ^{n
_2m+1}|n ₁≥n ₂≥…≥n _2m+1≥0} is (m+1)-multiple context-free, but not m-multiple context-free.

Originalsprache	englisch
Seiten (von - bis)	1-5
Seitenumfang	5
Fachzeitschrift	Theoretical Computer Science
Jahrgang	868
DOIs	https://doi.org/10.1016/j.tcs.2021.03.034
Publikationsstatus	Veröffentlicht - 8 Mai 2021

ASJC Scopus subject areas

Theoretische Informatik
Allgemeine Computerwissenschaft

Zugriff auf Dokument

10.1016/j.tcs.2021.03.034

https://www.sciencedirect.com/science/article/pii/S0304397521001870

Andere Dateien und Links

http://www.scopus.com/inward/record.url?scp=85104082520&partnerID=8YFLogxK

DK: Diskrete Mathematik
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Projekt: Forschungsprojekt

Dieses zitieren

@article{d65a8d9ea90742768853b9f23237f0e5,

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 n 1 a 2 n 2 ⋯a 2m+1 n 2m+1 |n 1≥n 2≥…≥n 2m+1≥0} is (m+1)-multiple context-free, but not m-multiple context-free. ",

keywords = "Formal language, Multiple context free language",

author = "Florian Lehner and Christian Lindorfer",

year = "2021",

month = may,

day = "8",

doi = "10.1016/j.tcs.2021.03.034",

language = "English",

volume = "868",

pages = "1--5",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Comparing consecutive letter counts in multiple context-free languages

AU - Lehner, Florian

AU - Lindorfer, Christian

PY - 2021/5/8

Y1 - 2021/5/8

N2 - 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 n 1 a 2 n 2 ⋯a 2m+1 n 2m+1 |n 1≥n 2≥…≥n 2m+1≥0} is (m+1)-multiple context-free, but not m-multiple context-free.

AB - 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 n 1 a 2 n 2 ⋯a 2m+1 n 2m+1 |n 1≥n 2≥…≥n 2m+1≥0} is (m+1)-multiple context-free, but not m-multiple context-free.

KW - Formal language

KW - Multiple context free language

UR - http://www.scopus.com/inward/record.url?scp=85104082520&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.03.034

DO - 10.1016/j.tcs.2021.03.034

M3 - Article

SN - 0304-3975

VL - 868

SP - 1

EP - 5

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Comparing consecutive letter counts in multiple context-free languages

Abstract

ASJC Scopus subject areas

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

DK: Diskrete Mathematik

Dieses zitieren