Decision problems for Clark-congruential languages

Makoto Kanazawa, Tobias Kappé
; 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v93-kanazawa19a, title = {Decision problems for Clark-congruential languages}, author = {Kanazawa, Makoto and Kapp\'e, Tobias}, booktitle = {Proceedings of The 14th International Conference on Grammatical Inference 2018}, pages = {3--16}, year = {2019}, editor = {Olgierd Unold and Witold Dyrka and Wojciech Wieczorek}, volume = {93}, series = {Proceedings of Machine Learning Research}, address = {}, month = {feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v93/kanazawa19a/kanazawa19a.pdf}, url = {http://proceedings.mlr.press/v93/kanazawa19a.html}, 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.} }
Endnote
%0 Conference Paper %T Decision problems for Clark-congruential languages %A Makoto Kanazawa %A Tobias Kappé %B Proceedings of The 14th International Conference on Grammatical Inference 2018 %C Proceedings of Machine Learning Research %D 2019 %E Olgierd Unold %E Witold Dyrka %E Wojciech Wieczorek %F pmlr-v93-kanazawa19a %I PMLR %J Proceedings of Machine Learning Research %P 3--16 %U http://proceedings.mlr.press %V 93 %W PMLR %X 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.
APA
Kanazawa, M. & Kappé, T.. (2019). Decision problems for Clark-congruential languages. Proceedings of The 14th International Conference on Grammatical Inference 2018, in PMLR 93:3-16

Related Material