Decision problems for Clark-congruential languages
This solves a theoretical problem for researchers in grammatical inference, but it is incremental as it builds on existing classes of grammars.
The paper tackled the decidability of equivalence for Clark-congruential grammars, showing it is decidable, and also proved that checking if a given deterministic context-free grammar is Clark-congruential is decidable.
A common question when studying a class of context-free grammars is whether equivalence is decidable within this class. We answer this question positively for the class of Clark-congruential grammars, which are of interest to grammatical inference. We also consider the problem of checking whether a given CFG is Clark-congruential, and show that it is decidable given that the CFG is a DCFG.