A Polynomial-Time Algorithm for Checking the Equivalence of Deterministic Restricted One-Counter Transducers Which Accept by Final State - Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing - page 134

When the stack reduction has applied to the node in question, the following (i) or
(ii) holds:
(i)

≤| α |≤| | | α | < | α | | β |≤| β |

1 Q 1 , and , 0 0 0

| α |≤| α | ≤| β |≤| | | β | < | β |

(ii) ,1 Q 2 and . 0 0 0

4.3 Skipping

In order to prevent the comparison tree from growing larger and larger infinitely
by successive application of branching or stack reduction steps, certain nodes are
expanded by other steps of skipping. Let the comparison tree which has just been
constructed up to a certain stage be denoted by T

( T 1 : T 2 ) .

α 1 ¯

¯

α 2 ¯

¯

Definition 10. If ( p 1 , α 1 γ 1 ) ≡ h 1 ( p 1 , γ 1 ) and ( p 2 , α 2 γ 1 ) ≡ h 2 ( p 2 , γ 1 ) are labels

of two nodes in T ( T 1 : T 2 ) which are connected by an edge labeled u 1 \ x 1 / v 1 ∈

Δ ∗ × ( Σ ∪{ λ } ) ∗ × Δ ∗ such that

σ ( u 1

=== ⇒
T 1

x 1 ) / σ ( v 1

=== ⇒
T 2

x 1 ) /

¯

( p 1 , α 1 ) ( p 2 , β 2 ) and ( p 1 , α 1 ) ¯ ( p 2 , β 2 ) ,

¯

x 1 ) ∈ Σ ∗ is the string ob-

with u 1 h 2 = h 1 v 1 , | β 2 |≥| α 2 | ,and | β 2 |≥| α 2 | ¯ ,where σ (

tained by eliminating all λ 's from x 1 , then we write

p 1 , α 1 γ 1 ) ≡ α 1 ¯

v 1
−−−−−−−→
T ( T 1 : T 2 )

u 1 \ x 1 /

( h 1 ( p 1 , ¯ γ 1 )

p 2 , α 2 γ 1 ) ≡ α 2 ¯

¯

( h 2 ( p 2 , γ 1 ) .

A sequence of such father-son relations as

p i , α i γ 1 ) ≡ α i ¯

u i \ x i / v i
−−−−−−−→
T

¯

( h i ( p i , γ 1 )

( T 1 : T 2 )

p i + 1 , α i + 1 γ 1 ) ≡ α i + 1 ¯

( h i + 1 ( p i + 1 , ¯ γ 1 )

with u i h i + 1 = h i v i ,for i = 1 , 2 ,..., m , is named a derivation path , and is written as

p 1 , α 1 γ 1 ) ≡ α 1 ¯

v
===== ⇒
T

u \ x /

( h 1 ( p 1 , ¯ γ 1 )

( T 1 : T 2 )

p m + 1 , α m + 1 γ 1 ) ≡ α m + 1 ¯

¯

( h m + 1 ( p m + 1 , γ 1 ) ,

v m . Here, “ ” may be omitted.

where x = x 1 x 2 ··· x m , u = u 1 u 2 ··· u m ,and v = v 1 v 2 ···

Definition 11. Suppose that a node in question is labeled

, ω 1 α ) ≡ , ω 2 β ) , ( p h ( p (5)

α = ω 1 α and β = ω 2 β with α = ε β = ε where or . We say that the prerequisite

for skipping to it is satisfied if the tree T ( T 1 : T 2 ) contains a branching node labeled