Paper Info
Title
Reductions In Tree Replacement Systems
Abstract
Certain kinds of Church-Rosser tree replacement systems ‘reduction systems’ are studied. Most results presented here generalize results proved for string rewriting systems by Book (1982). The concept of a tree rewriting system with a ‘norm’ is introduced and studied. A new ‘tree reducing machine’ which reduces every input tree to an irreducible tree is defined. As a consequence, when the norm under consideration is the size of the tree (the number of nodes), the word problem for finite Church-Rosser reduction systems is decidable in linear time (in the size of the input tree). Church-Rosser monadic reduction systems generalizing the monadic Thue systems of Book (1982) and Book et al. (1982) are also studied. It is shown that every congruence class and every finite union of congruence classes defined by such a system is accepted by a deterministic bottom-up tree pushdown automation. This new form of a tree automation is briefly studied.
Year
DOI
Venue
1985
10.1016/0304-3975(85)90089-1
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
word problem,Noetherian system,confluent system,Tree replacement system,congruence,tree automation with tree pushdown store,equation,normed rewriting system,reduction system,reduction,well-founded ordering,rewrite rule,Church-Rosser system
Journal
37
Issue
ISSN
Citations 
2
0304-3975
33
PageRank 
References 
Authors
2.38
9
2
Name
Order
Citations
PageRank
Jean H. Gallier1749111.86
Ronald V. Book21506234.41