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 130

∈ Δ ∗ ,let h − 1 w ht ,and wt − 1 Definition 7. For w , h , t = t if w = = h if w = ht .Then

h − 1 h Δ −∗ = {

∈ Δ ∗ }

Δ ±∗ = Δ ∗ ∪ Δ −∗ ,where Δ ∗ ∩ Δ −∗ = { ε } for Δ ,let , ,andfor

∈ Δ ±∗ ,let h − 1 ) − 1 Δ − + = Δ −∗ −{ ε } h ( = h . Moreover, let .

For k − 1 ∈ Δ −∗ with k ∈ Δ ∗ ,define k − 1 ∈ Δ ±∗ ,define | | = −| k | . Then for h

|

∈ Δ ∗ ,

h | if h

|| || =

h

k − 1

∈ Δ −∗ .

| | =

k if h

( , α )

Definition 8. Let p be a configuration of a dpdt T 1 which accepts by final

∈ Δ ±∗ .If ( , β )

state, p be that of a dpdt T 2 which accepts by final state, and h

hv x TRANS ( p , α )= h TRANS ( p , β )= { x / / v ∈ TRANS ( p , β ) } , then it is writ-

∈ Δ −∗ ,then

ten as ( p , α ) ≡ h ( p , β ) . Here, if h ( p , α ) ≡ h ( p , β ) is the same as

h − 1 ∈ Δ ∗ which stands for

k ( p , α ) ≡ ( p , β ) with k =

ku x

{ x / / u ∈ TRANS ( p , α ) } = TRANS ( p , β ) .

∈ Δ ±∗ or k ∈ Δ ∗ , is called Such a formula as ( p , α ) ≡ h ( p , β ) , h ( p , α ) ≡ ( p , β ) , k

an equivalence equation .
If TRANS

( T 1 )= TRANS ( T 2 ) , then the two dpdt's are equivalent , and it is written

as T 1 ≡ T 2 .Otherwise, T 1 ≡ T 2 .

3 Basic Properties and Propositions

(

z
−→ (

a /

For a droct T =( Q , Γ , Σ , Δ , μ , q 0 , Z 0 , F ) ,define τ = Max {| z | p , A ) q , θ ) ∈ μ }

{| θ | (

a / z
−→ (

and ρ = Max p , A ) q , θ ) ∈ μ } . Without loss of generality, we may assume

that ρ ≤ 2, i.e. stack height increases by at most one per one move.

3.1 Basic Properties of DROCT's Which Accept by Final State

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

× Γ ∗ be a configuration of T . Then, the followings (i) - (iii) hold. and ( p , α ) ∈ Q

β ∈ Γ ∗ .

(i) If N ( p , α ) = 0 with | α |≥| Q | ,thenN ( p , β ) = 0 for any

β ∈ Γ ∗ , it holds that (ii) For any

( , α ) ⊆ ( , αβ )

(a) L p L p and

( , α ) ⊆ ( , αβ )

(b) TRANS p TRANS p .

β ∈ Γ ∗ , it holds that

( , α )=

(iii) If N p 0 , then for any

(a) N ( p , αβ )= 0 ,

(b) L ( p , α )= L ( p , αβ ) and

(c) TRANS ( p , α )= TRANS ( p , αβ ) .

Proof. (i): It is clear because (See Ref. [1], Lemma 3.1, p.306 for the

details). (ii), (iii): It follows from Definition 5 since T is the dpdt which accepts by
final state.

Γ = { Z 0 }