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