2024-03-29T13:53:18Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:02001914
2023-08-03T00:46:51Z
312:313:314
Determinization of inverted grammar programs via context-free expressions
Nishida, Naoki
Niwa, Minami
Program inversion
Term rewriting
Context-free grammar
Regular expression
In this paper, we propose a determinization method of inverted grammar programs by means of context-free expressions (CFEs, for short) which are straightforward extensions (so-called μ-regular expressions) of regular expressions to context-free languages. Grammar programs are context-free grammars that an inversion method proposed by Glück and Kawabe uses as intermediate results. We use deterministic conditional term rewrite systems (DCTRSs, for short) as source and target programs, and our method aims at transforming a given DCTRS into a non-overlapping DCTRS that is computationally equivalent to the given one. To this end, we first translate a grammar program into an equivalent context-free expression. Then, by using some equalities of expressions, we transform the expression to a desired form. Finally, we translate the resulting expression back into an equivalent grammar program that can be translated back into a non-overlapping DCTRS.
journal article
Elsevier
2021-08
application/pdf
Journal of Logical and Algebraic Methods in Programming
122
100688
2352-2208
https://nagoya.repo.nii.ac.jp/record/2001914/files/Niwa-Nishida-20-jlamp.pdf
eng
https://doi.org/10.1016/j.jlamp.2021.100688
© 2021. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/