Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet

DOI10.1016/J.IC.2019.104442zbMATH Open1435.68153arXiv1805.04003OpenAlexW2970365824MaRDI QIDQ2280321FDOQ2280321

Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date: 18 December 2019

Published in: Information and Computation (Search for Journal in Brave)

Abstract: The famous theorem by Chomsky and Sch"utzenberger (CST) says that every context-free language $L$ over an alphabet $Sigma$ is representable as $h(DcapR)$, where $D$ is a Dyck language over a set $Omega$ of brackets, $R$ is a local language and $h$ is an alphabetic homomorphism that erases unboundedly many symbols. Berstel found that the number of erasures can be linearly limited if the grammar is in Greibach normal form; Berstel and Boasson (and later, independently, Okhotin) proved a non-erasing variant of CST for grammars in Double Greibach Normal Form. In all these CST statements, however, the size of the Dyck alphabet $Omega$ depends on the grammar size for $L$. In the Stanley variant of the CST, $|Omega|$ only depends on $|Sigma|$ and not on the grammar, but the homomorphism erases many more symbols than in the other versions of CST; also, the regular language $R$ is strictly locally testable but not local. We prove a new version of CST which combines both features of being non-erasing and of using a grammar-independent alphabet. In our construction, $|Omega|$ is polynomial in $|Sigma|$, namely $O(|Sigma{|}^{46})$, and the regular language $R$ is strictly locally testable. Using a recent generalization of Medvedev's homomorphic characterization of regular languages, we prove that the degree in the polynomial dependence of $|Omega|$ on $|Sigma|$ may be reduced to just 2 in the case of linear grammars in Double Greibach Normal Form.

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An elementary proof of double Greibach normal form
• Families of locally testable languages
• From regular to strictly locally testable languages
• Position-restricted grammar forms and grammars
• Title not available (Why is that?)
• An elementary proof of a generalization of double Greibach normal form
• The Missing Case in Chomsky-Schützenberger Theorem
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• A Chomsky-Schützenberger-Stanley type characterization of the class of slender context-free languages

Cited In (5)

• Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016
• Limited automata and unary languages
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• Regular languages as images of local functions over small alphabets
• From words to pictures: row-column combinations and Chomsky-Schützenberger theorem

Uses Software

• LANGAGE

This page was built for publication: Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet

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