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 131

From Lemma 1 (i) and (iii)(a), we can construct a checking procedure whether
any configuration

× Γ ∗ of a given droct T is N ( , α ) ∈ ( , α ) =

p Q p 0 or not since

| | +

it suffices to examine all configurations whose height is at most 1. Then, the

worst-case time complexity of this procedure is polynomial with respect to the de-
scription length of T .

Q

Lemma 2. Let T =( Q , Γ , Σ , Δ , μ , q 0 , Z 0 , F ) be a droct which accepts by final state,

× Γ ∗

and ( p , α ) ∈ Q be a configuration of T . If there exists a derivation such

x / y
=== ⇒
T

∈ Σ ∗ , ∈ Δ ∗ , ( × Γ ∗ , then there ex-

that ( p , α ) ( q , β ) for some x y q , β ) ∈ Q

x / y
=== ⇒
T

( n )

, β ) ists a derivation such that ( p , α ) ( q with n ≤| Q | ( | Q |− 1 ) for some

x ∈ Σ ∗ , y ∈ Δ ∗ , β ∈ Γ ∗ .

Proof. It is clear because Γ = { Z 0 } (See Ref. [2], Lemma 3.1, p.941 for the details).

From Lemma 2, we can construct a checking procedure whether any configura-
tion × Γ ∗ of T is live or not since for all configurations × Γ ∗ ( p , α ) ∈ Q ( r , γ ) ∈ Q

y
=== ⇒
T

x /

( n )

∈ Σ ∗ and y ∈ Δ ∗ ,it

such that ( p , α ) ( r , γ ) with n ≤| Q | ( | Q |− 1 ) for some x

∈

suffices to check whether r F or not. This procedure can be also performed in a

polynomial-time with respect to the description length of T .

3.2 The Basic Proposition Concerning the Equivalence

We shall check the equivalence of two droct's T i =( Q i , Γ i , Σ , Δ , μ i , q 0 i , Z 0 i , F i )( i =

1 which accept by final state, whose associated droca's are M i respectively. We

are only concerned with the case where L

, 2 )

( T i ) = 0 ( i = 1 , 2 ) .Let τ = Max { τ 1 , τ 2 } ,

where are constants depending on T i defined as above.

To begin with, we give the most elementary proposition concerning outputs.

τ i ( i = 1 , 2 )

Proposition 1. (i) Suppose T 1 ≡ T 2 holds and

w 1
=== ⇒
T 1

w /

( q 01 , Z 01 ) ( p , α ) with L ( p , α ) = 0 , (1)

w / w 2
=== ⇒
T 2

( q 02 , Z 02 ) ( p , β ) with L ( p , β ) = 0 , (2)

∈ Σ ∗ ,w 1 , w 2 ∈ Δ ∗ ,p α ∈ Γ 1 β ∈ Γ 2 for some w ∈ Q 1 , p ∈ Q 2 , and , then it holds

that

∈ Δ ±∗

w 1 h = w 2 for some h (3)

and

( p , α ) ≡ h ( p , β ) . (4)