Decision problems for Clarkcongruential languages
[edit]
Proceedings of The 14th International Conference on Grammatical Inference 2018, PMLR 93:316, 2019.
Abstract
A common question when studying a class of contextfree grammars (CFGs) is whether equivalence is decidable within this class. We answer this question positively for the class of Clarkcongruential grammars, which are of interest to grammatical inference. We also consider the problem of checking whether a given CFG is Clarkcongruential, and show that it is decidable given that the CFG is a deterministic CFG.
Related Material


