| Title: | On Unfolding for Programs Using Strings as a Data Type |
| Authors: | Andrei Nemytykh |
| Proceedings: | VPT 2014 EasyChair Proceedings |
| Editors: | Alexei Lisitsa and Andrei Nemytykh |
| Keywords: | program specialization, supercompilation, program analysis, program transformation, unfolding, Markov's normal algorithms, word equations |
| Abstract: | {Regular paper}
As a rule, program transformation methods based on semantics unfold
a semantic tree of a given program. Sometimes that allows to optimize the program or to prove its certain properties automatically.
Unfolding is one of the basic operations, which is a meta-extension of one step of the abstract machine executing the program.
This paper is interested in unfolding for programs based on pattern matching and manipulating the strings. The corresponding computation model originates from Markov's normal algorithms and extends this theoretical base.
Even though algorithms unfolding programs were being intensively studied for a long time in the context of variety of programming languages, as far as we know, the associative concatenation was stood at the wayside of the stream.
We define a class of term rewriting systems manipulating with strings and
describe an algorithm unfolding the programs from the class. The programming language defined by this class is algorithmic complete.
Given a word equation, one of the algorithms suggested in this paper results in a description of the corresponding solution set. |
| Pages: | 18 |
| Talk: | Jul 18 10:45 |
| Paper: |  |