A note on undercover relation

DOI10.1016/0020-0190(85)90124-3MaRDI QIDQ2265818zbMATH OpenOpenAlexFDO

Authors Erkki Mäkinen

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(85)90124-3

zbMATH Keywords

context-free grammarshomomorphism equivalencesemi-Greibach normal form

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

The paper gives a new characterization of the undercover relation between context-free grammars [see \textit{E. Soisalon-Soininen} and \textit{D. Wood}, Acta Inf. 17, 435-449 (1982; Zbl 0478.68086) for definition and motivation] in the semi-Greibach normal form (with right hand members of rules of the form \(b\alpha\), where b is a terminal symbol or it is empty and \(\alpha\) is a string of nonterminals). Based on this characterization (which involves homomorphism equivalence problem) it is proved that it is decidable whether a context-free grammar \(G_ 1\) undercovers a context- free grammar \(G_ 2\) with respect to a homomorphism (both \(G_ 1\), \(G_ 2\) are in semi-Greibach normal form).

Recommendations

• A hidden agenda
• scientific article; zbMATH DE number 2109445
• scientific article; zbMATH DE number 792655
• scientific article; zbMATH DE number 3905422
• scientific article; zbMATH DE number 970800
• Subverting deniability
• A note on the core

Cites work

• Associate languages and derivational complexity of formal grammars and languages
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• On a covering relation for context-free grammars
• On the decidability of homomorphism equivalence for languages
• Superdeterministic PDAs
• Test sets for context free languages and algebraic systems of equations over a free monoid

This page was built for publication: A note on undercover relation

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