Decision problems for Clark-congruential languages
Kanazawa, Makoto, Kappé, Tobias
–arXiv.org Artificial Intelligence
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.
arXiv.org Artificial Intelligence
Aug-21-2018
- Country:
- Europe > United Kingdom
- England > Greater London > London (0.04)
- Asia > Japan
- Honshū
- Kantō > Tokyo Metropolis Prefecture
- Tokyo (0.14)
- Chūbu > Ishikawa Prefecture
- Kanazawa (0.04)
- Kantō > Tokyo Metropolis Prefecture
- Honshū
- Europe > United Kingdom
- Genre:
- Research Report (0.50)
- Technology: