Bottom-up rewriting for words and terms

Details Bottom-up rewriting for words and terms Bottom-up rewriting for words and terms

2009-03-14

arxiv.org/abs/0903.2554v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

For the whole class of linear term rewriting systems, we define \emph{bottom-up rewriting} which is a restriction of the usual notion of rewriting. We show that bottom-up rewriting effectively inverse-preserves recognizability and analyze the complexity of the underlying construction. The Bottom-Up class (BU) is, by definition, the set of linear systems for which every derivation can be replaced by a bottom-up derivation. Membership to BU turns out to be undecidable, we are thus lead to define more restricted classes: the classes SBU(k), k in N of Strongly Bottom-Up(k) systems for which we show that membership is decidable. We define the class of Strongly Bottom-Up systems by SBU = U_{k in \} SBU(k). We give a polynomial sufficient condition for a system to be in $\SBU$. The class SBU contains (strictly) several classes of systems which were already known to inverse preserve recognizability: the inverse left-basic semi-Thue systems (viewed as unary term rewriting systems), the linear growing term rewriting systems, the inverse Linear-Finite-Path-Ordering systems.

Affiliated with

Also associated with

No associations

Rating

Bottom-up rewriting for words and terms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bottom-up rewriting for words and terms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bottom-up rewriting for words and terms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236031