Kanazawa, M;
Kappé, T;
(2018)
Decision problems for Clark-congruential languages.
In:
Proceedings of The 14th International Conference on Grammatical Inference.
Proceedings of Machine Learning Research
Preview |
Text
1805.04402.pdf - Submitted Version Download (242kB) | Preview |
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.
| Type: | Proceedings paper |
|---|---|
| Title: | Decision problems for Clark-congruential languages |
| Event: | 14th International Conference on Grammatical Inference, 5 - 7 September 2018, Wrocław, Poland |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | http://proceedings.mlr.press/v93/kanazawa19a.html |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10063347 |
Archive Staff Only
 |
View Item |
