[edit]

# Decision problems for Clark-congruential languages

; Proceedings of The 14th International Conference on Grammatical Inference 2018, PMLR 93:3-16, 2019.

#### Abstract

A common question when studying a class of context-free grammars (CFGs) 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 deterministic CFG.