A note on undercover relation (Q2265818): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Test sets for context free languages and algebraic systems of equations over a free monoid / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the decidability of homomorphism equivalence for languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Superdeterministic PDAs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Associate languages and derivational complexity of formal grammars and languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a covering relation for context-free grammars / rank | |||
Normal rank |
Latest revision as of 17:11, 14 June 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
0 references