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

DOI10.1016/J.IC.2019.104442MaRDI QIDQ2280321zbMATH OpenOpenAlexFDO

Authors Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date 18 December 2019

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

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)

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.

Recommendations

• The missing case in Chomsky-Schützenberger theorem
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• On the Chomsky and Stanley's homomorphic characterization of context-free languages
• Morphic characterizations with insertion systems controlled by a context of length one
• Chomsky-Schützenberger-type characterization of multiple context-free languages

Cites work

• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 871238 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3254902 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3316963 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A Chomsky-Schützenberger-Stanley type characterization of the class of slender context-free languages
• An elementary proof of a generalization of double Greibach normal form
• An elementary proof of double Greibach normal form
• Families of locally testable languages
• From regular to strictly locally testable languages
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• Position-restricted grammar forms and grammars
• The missing case in Chomsky-Schützenberger theorem

Cited in

(7)

• Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016
• The missing case in Chomsky-Schützenberger theorem
• Limited automata and unary languages
• Multidimensional trees and a Chomsky-Schützenberger-Weir representation theorem for simple context-free tree grammars
• 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

Describes a project that uses

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)