UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Decision problems for Clark-congruential languages

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 Green open access

[img]
Preview
Text
1805.04402.pdf - ["content_typename_Submitted version" not defined]

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 > 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 > Engineering Science Faculty Office
URI: http://discovery.ucl.ac.uk/id/eprint/10063347
Downloads since deposit
8Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item