A note on undercover relation (Q2265818): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:31, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on undercover relation |
scientific article |
Statements
A note on undercover relation (English)
0 references
1985
0 references
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).
0 references
context-free grammars
0 references
semi-Greibach normal form
0 references
homomorphism equivalence
0 references