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 = {Unold, Olgierd and Dyrka, Witold and Wieczorek, Wojciech}, volume = {93}, series = {Proceedings of Machine Learning Research}, month = {feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v93/kanazawa19a/kanazawa19a.pdf}, url = {https://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 %P 3--16 %U https://proceedings.mlr.press/v93/kanazawa19a.html %V 93 %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 Proceedings of Machine Learning Research 93:3-16 Available from https://proceedings.mlr.press/v93/kanazawa19a.html.

Related Material