Tree Rewriting System - Revision history

Polygon: Added Category:Functions

2026-02-28T11:58:50Z

Added Category:Functions

← Older revision		Revision as of 11:58, 28 February 2026
Line 131:		Line 131:
	== Bounds For Small n ==		== Bounds For Small n ==
	'''BBrw(1)=0''' because we can only start with a single constant a or b. It is already reduced to a single node.		'''BBrw(1)=0''' because we can only start with a single constant a or b. It is already reduced to a single node.

			[[Category:Functions]]

JackM4828: Fixed bound

2025-11-24T23:42:47Z

Fixed bound

← Older revision		Revision as of 23:42, 24 November 2025
Line 130:		Line 130:

	== Bounds For Small n ==		== Bounds For Small n ==
	'''BBrw(1)=1''' because we can only ~~consider τ=a or b,~~ with a single ~~rule being~~ a~~->a (infinite loop),~~ b~~->b (loop),~~ a~~->b (halt after one step), and b->a (halt after one step). Max(1,1)=1 (non-halters are discarded)~~.		'''BBrw(1)=0''' because we can only start with a single constant a or b. It is already reduced to a single node.

JackM4828: TYPO FIXED

2025-11-24T20:18:24Z

TYPO FIXED

← Older revision		Revision as of 20:18, 24 November 2025
Line 26:		Line 26:

	== Examples of Valid Trees and Their Graphs ==		== Examples of Valid Trees and Their Graphs ==
	'''a''' (single root ~~note~~ labelled a),		'''a''' (single root node labelled a),

	'''f(a)''' (an unlabelled root with a child a),		'''f(a)''' (an unlabelled root with a child a),

JackM4828: Removed ambiguous text

2025-11-23T22:11:28Z

Removed ambiguous text

← Older revision		Revision as of 22:11, 23 November 2025
Line 125:		Line 125:
	=== BBlt(n) ===		=== BBlt(n) ===
	“The largest tree size reached before BBrw(n) halts”		“The largest tree size reached before BBrw(n) halts”

	~~=== BBmt(n) ===~~
	~~“The max total nodes across all rewritten trees in BBrw(n)”.~~

	=== BBln(n) ===		=== BBln(n) ===

JackM4828: Typo fixed.

2025-11-23T22:08:29Z

Typo fixed.

← Older revision		Revision as of 22:08, 23 November 2025
Line 115:		Line 115:
	…		…

	This example also does not ~~terminate~~.		This example also does not halt.

	== Functions ==		== Functions ==
Line 121:		Line 121:

	=== BBrw(n) ===		=== BBrw(n) ===
	“The maximum number of steps before halting, taken over all initial trees τ of size ≤n and all rulesets of size ≤n, with each rule part (L→R) also having size ≤n.”		“The maximum number of steps before halting, taken over all initial trees τ of size ≤n and all rulesets of size ≤n, with each rule part (L→R) also having size ≤n.” (We assume that each rule part can have different lengths (but must be ≤n))

	=== BBlt(n) ===		=== BBlt(n) ===

JackM4828: Created a page that deals with a tree rewriting system

2025-11-23T22:06:52Z

Created a page that deals with a tree rewriting system

New page

== What is a Tree-Rewriting System? ==
A Tree-Rewriting System (TRS for short) is a computational model that defines a transformation between hierarchical structures (trees, often representing terms or code) by repeatedly applying a set of specified rewrite rules.

== Definition ==
We define an alphabet Σ={a,b,(f,f’,f’’,…)}. We can define terms built from these symbols as follows:

- a is a leaf node (constant),

- b is a leaf node (constant),

- f() is a unary function (has 1 child),

- f’() is a binary function (has 2 children),

- f’’() is a ternary function (has 3 children),

…

and so on…

…

In general, f’’…’’() (with n total apostrophes) is an (n+1)-ary function (has n+1 children)

'''''NOTE:''''' each function symbol specifies its arity.

== Examples of Valid Trees and Their Graphs ==
'''a''' (single root note labelled a),

'''f(a)''' (an unlabelled root with a child a),

'''f’’(a,f(a),b)''' (an unlabelled root with three children. The middle child (unlabelled) has a child labelled a,

'''f’(a,b)''' (an unlabelled root with two children labelled a and b),

'''b''' (single root note labelled b),

'''f’’’(f’(a,b),b,b,a)''' (an unlabelled root with four children, the first child has two children a and b. The other three children of the root are labelled b,b, and a.
[[File:Examples of Graphs .jpg|thumb]]

== Rulesets in Tree-Rewriting Systems ==
We consider τ to be an initial valid tree.

A deterministic tree-rewriting systems ruleset R consists of pairs of trees (L→R) where the leftmost instance of L (in τ) is replaced with R. We allow duplicate rules in the same ruleset, and rules are followed in cyclic order (initially rule 1).

If a rule does not apply, simply skip it and move to the immediate next one in R. Skipping a single rule counts as one step.

== When Does Halting Occur? ==
We can say that halting occurs in one of the two following scenarios:

τ has been reduced to a single constant,

or,

There does not exist a rule in R that can further transform τ.

== The Tree-Rewriting System In Action ==

=== Example 1: ===
τ: f’(a,f(b))

R: a->b, b->f(a), f’(a,b)->b

f’(a,f(b))

f’(b,f(b)) (as per rule 1)

f’(f(a),f(b)) (as per rule 2)

Skip rule 3

f’(f(b),f(b)) (as per rule 1)

f’(f(f(a)),f(b)) (as per rule 2)

Skip rule 3

f’(f(f(b)),f(b)) (as per rule 1)

f’(f(f(f(a))),f(b)) (as per rule 2)

Skip rule 3

…

This example does not halt.

=== Example 2: ===
τ: f’(f(a),f(b))

R: a->f’(a,b), f(b)->b, f(a)->f(b)

f’(f(a),f(b))

f’(f(f’(a,b),f(b)) (as per rule 1)

f’(f(f’(a,b),b)) (as per rule 2)

Skip rule 3

f’(f(f’(f’(a,b),b),b)) (as per rule 1)

Skip rule 2

Skip rule 3

f’(f(f’(f’(f’(a,b),b),b),b)) (as per rule 1)

Skip rule 2

Skip rule 3

f’(f(f’(f’(f’(f’(a,b),b),b),b),b)) (as per rule 1)

…

This example also does not terminate.

== Functions ==
From here, we can define a multitude of functions analogous to the classic Busy Beaver. We say that a “size-n tree” consists of n total nodes. Examples include: f(a) (contains two nodes), a (or b) (contains one node), … etc …

=== BBrw(n) ===
“The maximum number of steps before halting, taken over all initial trees τ of size ≤n and all rulesets of size ≤n, with each rule part (L→R) also having size ≤n.”

=== BBlt(n) ===
“The largest tree size reached before BBrw(n) halts”

=== BBmt(n) ===
“The max total nodes across all rewritten trees in BBrw(n)”.

=== BBln(n) ===
“BBrw(n) but with n total distinct leaf nodes allowed in its alphabet Σ”

== Bounds For Small n ==
'''BBrw(1)=1''' because we can only consider τ=a or b, with a single rule being a->a (infinite loop), b->b (loop), a->b (halt after one step), and b->a (halt after one step). Max(1,1)=1 (non-halters are discarded).