9512.net

# A Matrix q-Analogue of the Parikh Map

A MATRIX Q-ANALOGUE OF THE PARIKH MAP
Omer Egecioglu
? ? ¤ ¤ ? ? ? ? ?  ¤ ? ?  ? § ¤ ?? ? ? ? ?

Department of Computer Science University of California, Santa Barbara CA 93106, USA
omer@cs.ucsb.edu

Oscar H. Ibarra

Department of Computer Science University of California, Santa Barbara CA 93106, USA
ibarra@cs.ucsb.edu

Abstract

We introduce an extension of the Parikh mapping called the Parikh -matrix mapping, which takes its values in matrices with polynomial entries. The morphism constructed represents a word over a -letter alphabet as a -dimensional upper-triangular matrix with entries that are nonnegative integral polynomials in variable . We show that by appropriately embedding the -letter alphabet into the -letter alphabet and putting , we obtain the extension of the -dimensional (numerical) matrices introduced by MaParikh mapping to teescu, Salomaa, Salomaa, and Yu. The Parikh -matrix mapping however, produces matrices that carry more information about than the numerical Parikh matrix. The entries of the -matrix image of under this morphism is constructed by -counting the number of occurrences of certain words as scattered subwords of . Parikh mapping, Parikh matrix mapping, scattered subword, injectivity, morphism, -analogue.
 ? ¨?? § ¤

Keywords:

1.

Introduction

Parikh’s theorem [7] says that every context-free language is “letter-equivalent” to a regular language. More precisely, the commutative image of any contextfree language is always a semilinear set, and is therefore also the commutative

Work done in part while on sabbatical at Sabanci University, Istanbul, Turkey during 2003-2004. Supported in part by NSF Grants IIS-0101134 and CCR02-08595.

?

 

where denotes nonnegative integers and The Parikh mapping is a very important concept in the theory of formal languages. Various languages accepted (generated) by automata (grammars) more powerful than pushdown automata (context-free grammars) have been shown to have effectively computable semilinear sets. For example, it is known that every language accepted by a pushdown automaton augmented with reversalbounded counters (i.e., each counter can be incremented/decremented by one and tested for zero, but the number of alternations between nondecreasing and nonincreasing modes is bounded by a ?xed constant) has a semilinear Parikh map [4]. The fact that the emptiness problem for semilinear sets is decidable implies that the emptiness problem for these automata (grammars) is decidable. This decidability of emptiness has been used to show the decidability of many decision questions in formal languages (e.g., [3]) and formal veri?cation (e.g., [5]). The Parikh matrix mapping introduced in [6] is a morphism

where is a collection of -dimensional upper-triangular matrices with nonnegative integral entries and unit diagonal. The classical Parikh vector appears in the image matrix as the second diagonal. The Parikh -matrix mapping introduced in this paper is a morphism

where is a collection of -dimensional upper-triangular matrices with nonnegative integral polynomials in as entries. The diagonal entries of are which readily encodes the Parikh vector. Moreover if we embed into in the obvious way, and put , then we obtain the matrices of the Parikh matrix map of [6]. Thus, viewing as a word in with , evaluated at is precisely the the Parikh -matrix dimensional numerical Parikh matrix . It is a basic property of the Parikh matrix mapping that two words with the same Parikh matrix have the same Parikh vector, but two words with the same Parikh vector in many cases have different Parikh matrices [1]. Thus,

S PD RP( &' &" G  GQIP( C &" HF( ' &" B ?ED?" C4  & G & B ? A @8 ? 64 9 7 5 D?" B h` 4 ¨ Y?? X? D e ? ?c F & f? ??bRa? B ( C &" ? y?
? ? ?

" 31 2 ! ? ?§???? ?   ?  ¨?¤ ? ?
in

image of some regular set. Consider the alphabet and for , de?ne by the number of occurrences of Parikh mapping is a morphism

D " R T ? ?g B 4 D ?" B ¨ X `h 4 ¨ Y??? e X ? ? # ??" ? e ?g D R w svu s?g G  G I w xu tg G F w vu tg B  s s s s g a Dp qB ? Vi7 ? 5 `h 4

D fdbB e c a ¨ Y? X W7 ? 5 R U4 T V

) & 0( ' &"

?

. The

g

? # %\$" g

D ` g B rV

¨ X ` \$V

9A

D B ?" C4

the Parikh matrix gives more information about a word than the Parikh vector. The injectivity of the Parikh matrix mapping is investigated in [1]. From our construction it is easy to see that two words with the same Parikh -matrix have the same Parikh matrix (and therefore the same Parikh vector), but there are cases in which two words with the same Parikh matrix have different matrices. Thus the Parikh -matrix gives more information about a word than the Parikh matrix. The basic idea in the construction of the entries of the Parikh -matrix image of is -counting the number of occurrences of certain words as scattered subwords of . The paper has ?ve sections in addition to this section. Section 2 gives some basic notation and de?nitions. Section 3 recalls the notion of a Parikh matrix mapping introduced in [6] and the fundamental theorem concerning these mappings. Section 4 presents our new Parikh mapping, called -matrix mapping, that generalizes the Parikh matrix mapping: whereas the latter produces matrices with nonnegative integer entries, the former produces matrices with nonnegative integral polynomials (in variable ) entries. This extended mapping produces matrices that carry more information about the mapped words than the numerical matrices produced by the Parikh matrix mapping. Section 5 presents the main results, including Theorem 8, which gives the main properties of a -matrix mapping. Section 6 looks at some matrix operations such as injectivity and inverse concerning -matrix mapping.

2.

De?nitions

We start with some basic notation and de?nitions. Most of these are as they appear in references [6] and [1]. The set of all nonnegative integers is denoted by . We denote by the collection of polynomials in the variable with coef?cients from . denotes integers, and denotes the ring of polynomials in the variable with integral coef?cients. For an alphabet , we denote the set of all words over by and the empty word by . We use “ordered” alphabets. An ordered alphabet is an alphabet with a relation of order (“ ”) on it. If for instance , then we use the notation If then denotes the length of . For and the number of occurrences of the letter in is denoted by . Accordingly . Let be an ordered alphabet. The Parikh vector is the vector of occurrences . The Parikh of mapping
?

1   ' y¨ 1   1  ! ?? G `S G ? G ¨ §?? ¨ SS  ?¤ ?

g

g

?

?

? A @7 ? 64 5 9 D R ( ' &" G  G I ( ' &" G H( C &" B &  & F & ! ? f ? ?  &  R ( ' &" c  " 21 )P( &C &" ??# " ??# 2t1 " S ! ? ? U?§??   ?  ¨?¤ ?

g

§

g

g

??g ? ?¤¤

g

?

?

g

?

¤?¤ ? ? ?g ? 9A 9A

g

g



? # " ? ? ?  f ¨ §¤ f? I & F & & c P( C &" c ( C &" ? ' &"

& ' &"

"

g

?

?

? W" #

g

9A

"

is de?ned by setting

Let be words over . As de?ned in [6], the word is called a scattered , where desubword of if there exists a word such that notes the shuf?e operation. If , then the number of occurrences of in as a scattered subword is denoted by . Partially overlapping occurrences of a word as a scattered subword of a word are counted as distinct occurrences. For example, , . Notation: We shall also ?nd it useful to denote , , and notation, we write . Notation: Consider the ordered alphabet As in [6], we denote by the word by . Using this for any letter

where

For motivation and further issues about the Parikh mapping as well as languagetheoretic notions not considered here, we refer the reader to [8].

3.

Parikh matrix mapping

We ?rst describe the extension of the Parikh mapping to matrices as originally de?ned in [6]. The extension involves special types of triangular matrices. These are square matrices such that , for all , , for all , and moreover, , for all . The set of all these matrices of dimension is denoted by . Thus is the collection upper-triangular matrices with entries from and unit diagonal. The set is a monoid with respect to multiplication of matrices and has a unit which is the matrix . The main notion introduced in [6] is as follows: where Let be an ordered alphabet, . The Parikh matrix mapping, denoted by , is the morphism:

,

are zero.

?

??? ?4 i

Let matrix mapping

be the ordered alphabet represents each word over

as a

. Then the Parikh upper triangular

' e ? 22

C

? R? ? !  1 §? ? §¤ D ¤1 B R v4 p i e c a 5 7 5 ?'?6tBe

de?ned as follows: If , then for each and all other elements of the matrix

`@V ? 2 ' 2?C 4' e 9A # 2

a

where

.

e

2 3a

? ¤?

41 5 @ 5 7 1 6      10   BA9! 8?e  ?y???¨ ¨ §2X1 ¤ 1 2 1 5

'  (u &

( §  e ? ! ?? ( ? & 1 %\$ &1 )& ? )' 0( C &" v0( (u &  ? & ?( ¨§? C &" `

C

?

X V G ¨ Y? W7 ? 5 R U4 T R T y4 ! ? r@ r ?§¤ r? ?   ? ¨? ?

 ? & ?( ¨§??C &" ? # "G ? ? ? ?¤?? ?# " ? S R &  G & GF & PD P( C &" G  QI ( ' &" §H( ' &" B E" C4 ? D B
a `

5 ¨ 2 @ 5\$ D 4a ' 2 EDID 7 4 ' ?C HGe C B ?

`

T

" ( & #? ! ?? ( §? ¤ &1 ' (! e ? ! ( b1§ (

?

?

¨s¨ X ` rD 4 ' 2 ED¨ D 4 ' 2 C B q

` V a Sa R

& 0? ! ( ' )!!§ ( & "

4' 2 1

? ? 4' 2

? p UD ¤1 B e R

C

e ha 2 g a Y Y YXV Hcfebdcba`WU

"

a

? V?? ??x ?\$?(?yw

a

57 5 9QG Pe 5 7 5 F@ 0Be

"G

` rV

i 64

? ¨ X p ' uC p

?

? # ?v2 1

"

?
9A

.

,

?     ! ? ?   ? ? ? \$   ? ? "?  ?    ?   # ?   # ?      ? ?  #  "? #   ?   ! "?    #?   ! ?   ! "? ?   ! ?                    #? ?    "?    #"?    ? ? 

Remark: The Parikh matrix mapping is not an injective mapping. For instance one has over the ordered alphabet

SD B Pt1 ? TU4 DH F4 Y B ? U4 31 QF4 B? T D T D B? T D T D T D  B ? 4 Y B ? U4 31 B ? 4 T
and

? 3Y `1 B ? T D1  ? D  ¤1 B ? U4  QF4 T

Thus

matrix with unit diagonal with nonnegative integral entries. We compute some special cases.

Conditions for two words and to possess the same Parikh matrix was studied for the binary alphabet in [1]. We will discuss some of these conditions later in the paper. The main property of the Parikh matrix mapping proved in [6] is the following theorem:

2

1

?

    
? ? ?

! ?"??     "?

 



¨?& ¤ ?'§? ?? ?




¨&? ¤ '?§? ?? ?

! Q ?§¤    1

?



!
? ? ?

 

?   #  ! ? ?  ) ) "?   0 0 )   ? 



?

#  ?    ?    ?   ? ?   ! %%?    \$ \$ "?    %%? ?   \$

?&¨ ¨? ¤ ? '(?? I ?§? ???




 
 

?      ! ?%?  %\$  \$   %%? ? ?   # ?   ## ?       ? #   ?   ! ? #  ? ?   ! ? ?   ! ?               "?    #"?    ? ?



and consequently
  

?&¨? ¤ ('?§? ?? ?
and

¨ ¤ ? I ?§? ???
?

D D B D D B  G D § B  31 BC % ¤1  B G Y`1 C B  H\$1  B G ¤1 D %\$1 B  D § B "  B  ? `1 C %\$1  " 89! 7(&'u ? ' % ED g B ! cu &
, the relevant factorizations of

A s 8 s X @ s 7 tg s

"

? @G

"
?

7

F ? ? " )0? " \$#\$## 0 )( ('u ?( ) " &

F ? ? sw F ? ? " s X ? sw ? " s X \$#\$#¤X F )? sw F )? " s X ) sw ) " s g # a 

@

F ? ? sw F ? ? " s X ? sw ? " s X \$#\$#¤X F )? sw F )? " s X ) sw ) " s g # e c @ 5 ! f?P5 ¨ X 4 ? 4 1 4  ¨ 2X 1 ¨ X 2 1 2 ? f" ? 2? ?

4' D g B ? ¨§0( (u & )' " 2 ?1 ' " ? ? § 0( (u & ) g ? # ?W" G 4 ' 2 1 ' e a 5 @  D g ) cu B ? ¨§P( &  ' S S ' ' S &  I & F & PD R ( ' &" G  G P( C &" G ( C &" ? D ? B E?" B 4 ED ¨ X ` ` C G S G  C G  ¨ C B " D ¨ X ' S ' G ' D ?" B R ?4 i ` ` C G ?S S ? G   C  ¨  C ? B  ¨ §¤ ? ? !   ?  ? ? ? ? ? (f ¤f 
?

([6], Theorem 3.1) Let an ordered alphabet, where and assume that , has the following properties

? 6" # ! ? ?    ?  3§¤ ? ?   ¨?
?

in , and add up these monomials. Note that the last term in the exponent in (2) is de?ned. Thus

? # ¨ X41

7

?

??

indexed by pairs Next we introduce a collection of polynomials of words , with . These polynomials will “ -count” the quantities de?ned above for general and as will be explained shortly in the case is a scattered subword of . To construct , we consider each factorization

' ? ¨§)P( cu #? ¨ X 4 ' 2 C & a 5 ?5 86e @ 7 5 ' D e a 7 5 cybB 5 86e e ?22 C D efc bB 97  @??e ? f? 4 ' 2 C a 5 5 ¨s¨ X ` qrD 4 ' 2 DE¨ D 4 ' 2 C B E?" B R 64 ? D i ? ?V? ? ?r¤f V ??
e

2

a

with

4.

([6], Corollary 3.1) Let has the second diagonal (i.e., the vector trix the Parikh vector of , i.e.,

As a corollary

1.

3.

2.

Suppose and for ,

! 5 5 3 §¤ \$? 6 4 2 ? ?

?

? ?" #

%

For example for

-counting scattered subwords

for

, for all

, for all

, for all

, and construct the corresponding monomial

,

,

.

and

since

be . The matrix

are The ma, so that . Then (3) (2) (1) )

 ? 4' 2 1 0 V?? ? ?x 1\$?(?yw &
? ?g ? 9A

? D g B ? ¨§P( cu )'

? ?#

We denote by the collection of -dimensional upper-triangular matrices with entries in . Let denote the identity matrix of dimension . The matrix corresponding to a is de?ned as the matrix obtained

a

This is the sense in which the polynomials “ -count” the number of occurrences of as a scattered subword of . These polynomials are the “ -analogues” of the numbers .

a 

@ 7 5 A5 Q?e

? ?# p 1 D \$1 p T ?g ? 9A B h 4 ? ? ` Dg a B rV `  ? ¨§0( (u & )' 4 0 ¨ 2X 1 2 1 g " 1 g D g B ? § 0( (u & )' S )  §& PDQ? §¨0(?? ( ¨? ' &" ? B ? § 0( (u #ED ?B ? § 0( (u & )' & ? e )' ! ?  ? ??§?? ?     ¨?¤ ? g a Y  HcfebdY f S ? ¨ X ? X ? g B )! ( cu g ? g D § '
Parikh -matrix mapping

?f ce?


D D D G `1 B B  D § B  H B 1 Y B "  B  `1 C %\$1  ? " 7 &u ? 8 §§ 9! ( ? D § ' % ? g B )! ( cu & ¨ s s A s s @ s 7 s sw s g ? X 8 X X ? ? ?# "  `f? 4 ' 2 1 1 ¤ ?? 6 4 2  ? ? @ G e ? 7 ! 5 5 3§¤ \$? ? V ? ? ? ? x \$?(?yw S Q g c  Q" c f? ¨ X ? X ¨ g c ¨ X  X ? g c ¨ X ¨ X ? g c ¨ X ? X ? %ED g B )! cu & g g g ? §'
Suppose and for , , the only relevant factorization of and is
?

 D1 D D D B D D B  D G D`1 B B  D § B  H¤P B G ¤1 B B  Y%¤1 B  D § B G ¤1 D  B  H\$1 B  D § B G `1 C % B  31 B  D § B "  B  `1 C %\$1  ? " 7& ('u ? 8 §§ 9! % ED g B )! (u & ? §' ¨s s As s @s 7s g ? X 8 X ? # ??"   ? 4' 2 1 ¤?? 6 4 2  ? ? @ G " ? 7 ! 5 5 3§¤ \$? ' ? V ? ? ? ? x ?\$?(?yw S  g c  Q" ?? X  g c ¨ X ¨ g c  X ?f? D g B ! cu & g ? ? g
Suppose and for , , the relevant factorizations of and are
?

Since the summation in the de?nition (3) is over all occurrences of as a scattered subword, the following proposition is immediate:

and therefore

For example for

and therefore

For example for

and therefore

. Then

. Then

in

"

4' 2 1

&

5.

Let

and

. Then

     

? ? Dt1Y `1 Bh 4 ? D   `1 B 4 h
Thus

? g
 

?



e ? ! ? ? ee  ? ? e g ? ! g g cc ee  g g

g ?  ! ? e ? ?   ? ? ! ee g ? ?


? ? ?  ! ee g e   ? ? ? ? ?  ! ee g e   ? ?

g ? ? ! g g ? g Q"  g g  ? ? ? ?  ! e? e ? e   ? e g ? ? ? ?  ! e? e ? e   ? e g

SD Pt1 D D D D1  D  D D  B h 4 H B h 4  B h 4 t1 B h 4 ? 3Y ¤1 B h 4 B h 4  B h 4 t1 B h 4 ? D  `1 B h 4 S PD p V qB ? i7 ? 5 h 4 g D g B ` V
Thus the Parikh -matrix mapping is a morphism

?

from ?rst by changing the -th diagonal element from 1 to . Then if , we also change the entry immediately to the right of the from 0 to a 1. Thus , then if

Remark: Just as the Parikh mapping is a morphism from the monoid to the monoid , the set of matrices is a monoid with respect to matrix multiplication and as its unit.

`

T

D § G G ? B
?

D SS qD ? G S G ? G ? B G c G 9A B `

?



g ? ? ? ? D ?  EH B G ! e g ! ? ? e? e  h 4  e? ?
are zero.

 a v?

g

g

& y &? a g ? `h 4 D ¤ h  4   ¨ D §8" ¨ B h 4 D ?" B h 4 ? t?" v8" ?" B h 4 T ` H? D § B h 4 ? ? ? e ? ?? ? D D ?  ? Y B G ! ?  E31 B 4 h 4  ? ee g  h e  ! 4  2  §?? ? ?¤ D ¤1 p Bh 4 'p  a v? e ? ¨ X p ' uC ??? ??7 G a 5 78?e e ? 2 ' 2 C 5 g p f? p uC D 4 ' 2 ED¨ D 4 ' 2 C ? p B ED ¤1 B h 4
We extend the mapping from

?

`

When the alphabet is

`T

3.

4. all other entries of the matrix

1.

2.

1.

,

for

if

,

¤  ¨ 5 ? 5 ? # ?r§?e G ?v2 " D ?" B h 4 
,

As examples, we have We will refer to rameter , which is 2.

as the Parikh -matrix mapping. Note that the pais implicit in our notation.

,

and ,

to

, then

by setting

Consequently, for

Remark: For the Parikh -matrix mapping it is not true that if is a contextfree language, then its image is some suitable extension of the notion of semilinearity to matrices over . This is a direct consequence of Theorem 9 and the negative result concerning the Parikh matrix mapping ([6], Remark 3.2).

is

Proof The matrices are all upper-triangular. It is easy to see that the diagonal entries of a product of two upper-triangular matrices depend only on the diagonal elements of each of the matrices. Since diagonal matrices commute, and each occurrence of the letter in has the effect of multiplying the -th diagonal entry of the -dimensional identity matrix by , the result follows immediately.

with respect to at

. The matrix

2.

, for all

Proof The proof of the parts 1. and 2. are immediate. We now prove property 3. Assume that . The proof is by induction on . If , the assertion

e

5 ¤

¤

¤ & ?? C &"

C

3.

, for all

a 

@ 7 5 A5 8?e

a

4' D g '(u B ? § )0( &#? ¨ X ' 2 s g ) w v su ? 2 2 ? f? 4 ' 2

1.

, for all

,

, .

`

a

57 5 986e 5 @ 5 97  A6e

?

Let and assume that the following properties

D 4 ' 2 DE¨ qDDg 4 ' ? D ? B 2 C B 8?" B h 4 ! ? ? ? %# ?§¤" %? ?  ?  ¨? ?

? e g ? ?g ? # D R w x su g G  G I w v su g G F w x su g B s  s s ` ? 9A "

Remark: We note that the Parikh vector of of .

is given by the formal derivative

be an ordered alphabet, where , has

?

g

? # "

Let vector of diagonal entries of the matrix

and

?

? ?g ? 9A ? g g ? ? g g g ?  ? ! g  g c g c g g g   c  Q" c g c  Q" ? ? g ? ? e D g ?  ? ?" B 4 ! g g ?  ! g g gQ"  g g c e g g  h    c e  1  `1  `f"  1 ?
, we compute that

`

T

D \$1 B 4 p S ??g ? 9A # D R w v su g G  G I w x su g G F w v su g B s  s sh ` D " ! ? ? B  h 4 ? ?§¤ ? ? ?  ? ¨? "

p 1

a

? cfebdY f ce? a Y  ?f
g

? ?V? ? ?r¤f V ??

C

C

e

?

2



. Then the

a

 

)' u ) (' u )' u @  86e ? D g B ? ¨§P( ? & c D g B F  ? ¨§) P(? u & ? D g B ? § 0( ) ? ( ' ? & u 7 5  ' G@ 7 5  A5 8?e ? D g B F ? § 0( ' & g ? D g B F ? ¨§P( )?( ? & ) (u ' D ?? g B C ? ¨§0( ? ' & ? C 4' h 4' h 4' @ 5 7 5  A98?e ? ¨ X ?2 C c ?2 C ? ¨ X 2 C G A5 8Pe ? 4 ' ?2 C g ? 4 ' 2 C @ 7 5  D ' ¨ED¨ D ' §C ? ? ? ? ` h h ? B     ? ? ' R sw su g   ? e   ! ` ¨  ? `? C ? ? SS e g S ? S SS ' ¤C   sw su g ?  ?   ?   I    ?   ? e   ` ' ¨ ? C    ' ?¨ ? C F sw su g      ` ?  D ?" D g D @ G @B Bh 4 ? ? e c f@ G @B T `   ? ? ! e  ? 4 ? SS S SS e g S ?  ED 1 B h 4      ? e    ?  ? a  @ a ? D ?" B @ 4 a @   h    ? ?

'R ! ` ¨  ? `?
. . .

? ? ?  
  

' ` ' ¨ ?? C ` ¤C
? ?# 4 1

   

 ? D? "B 4 h  I sw su g  ?     ' ?¨ ¤C F sw su g  ? ?
Assume that

holds. Assume now that part 3. holds for all words of length and let length . Write where and . Then

"

D41 D B h 4 D ? " B h 4 ? ?" B h 4 4 1 ?%f" ¤ ? ?? & ? &" ? " ?

¤

. . . . . .

. . . . . .

. . . . . .

. . . . . .

C

sw su g

By the inductive hypothesis the matrix two cases depending on whether , or

where the matrix differs from only in two entries: The entry in position is , and the entry in position is 1. Let . Then

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

has property 3. The proof has . For , we have

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

be of

. . .

 



. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

!

and for all other indices, de?nition of the polynomials

e fc

¤

If

, then

. But these are immediate from the which satisfy

and are unchanged otherwise. In the case the only change that appears in going from to is that the last column is obtained from by by . This corresponds to multiplying the elements of the last column of the fact that the number of occurrences of in in any factorization of the form (1) is increased by 1: i.e.,

and the proof follows by induction.

Remark: The structure of how the polynomials in the matrix are indexed can be mnemonically recorded as shown below in the case of the four-letter alphabet :

As an example, the entry in second row and the fourth column is a shorthand for the polynomial , the -count of the number of occurrences of as a scattered subword of as developed in section 4.

Then at

, this vector evaluates to

Proof This proposition is a special case of a stronger result that characterizes the whole matrix at that we give as Theorem 9.

. Then

Proof Combine Theorem 8, Theorem 3, and Proposition 1.

?

e D?" ? B

D ?" ! ¨ X ? h 4 ?  ¨ 1 B 1  ! ?` ?  ` ? ?  

D ?" B R 4 ? ?g gT X `  ? ?9A  ¨ §?? 1 1¤ ?  t§¤ ? ? ¨?

Suppose as a word over resulting Parikh -matrix in Parikh matrix .

and . Consider and let be the evaluated at is the

?

g h 4? # "

?

? ?" #

Let vector of super diagonal entries of the matrix

and is

. Suppose the

?

? ?

?

S ¨  ?g # qD g B ` ' ¨  ` C G  G g B  '  C G D g B  ' ¨ C B ? D  D ` ?? 9A D" ! B ? h   ' ?§¤ ? ? 4   ? ¨? ? ?

 



? s ?w v su g !  1 1  1  1 ??1  0¨ 1

g

D g B F  R § F ( ' ? u & f? g B F  R § F ( ' R ( ? u g D

¨ X

S R &  I & GF & PD F  P( C &" G  G P( C &" §( C &" B

`? ` ?

?

?

? s w v su g ? 1  01 1¨

a ?

1

@

? ? ? 1 ? ?   1 ? 1 I w sv su g s ¨1 F w x su g  ¨ 1 !?? Q?  ? ??Ut§??  ¨?  ¨?¤ ?

g

? e yg

"

' D g Q? ( P( (u B I

D?" Bh 4

&

?

&

? ?

a Y  ?f cfebdY f ce?
e ? g
¤ ?

?V? ? r¤f V ??

 Y 1 1


"

6.

Injectivity, inverse, and further remarks

Just as the Parikh matrix mapping, the Parikh -matrix mapping is not an injective mapping either. For instance over the ordered alphabet one has

However, there are instances in which two words can have the same Parikh matrix, but distinct Parikh -matrices. The injectivity of the Parikh matrix mapping was studied in [1]. In particular it was proved that over a binary alphabet , a pair of palindromic amiable have the same Parikh matrix image. The de?nition of palindromic words amiable pair is as follows:

(4)

The corresponding matrices given by the Parikh -matrix mapping are calculated over the alphabet in accordance with Theorem 9. These are also upper-triangular matrices, but with entries from . They are given by

(5)

(6)

Clearly, these two distinct matrices reduce to given in (4) as guaranteed by Theorem 9. Thus the matrices obtained by the Parikh -matrix mapping contains ?ner information that is able to distinguish words that are equal under the ordinary Parikh matrix map. An alternate generalization of the Parikh matrix mapping with additional injectivity properties using

¤

R

¤

For example the words and over palindromic amiables. Therefore as proved in [1], they have the same Parikh matrix image. We calculate directly that indeed

D x2 B I U4 ? v1 B I T 4 D T g e !  g c  g c ce g c e ?



h 4

? ? ?g ? 9A

g ! g Q" e c e gc   c

! §  0 §¤  1 g e ? ? Dx2 D B I U4 ? ! "? e ? ?  ? v1 B I 4 T T  e 

e

? g g c g c g ? g  Q"  c g

1   1 ¤r? 1 1

g  Q"

c g

?

?

? 

?

? 

?

g 

g 

? x2 B 4 D h

? Dv1 Bh 4

¤

2

R

¤

1

2.

and

have the same Parikh vector, i.e.,

! 2 ?§¤ ? ? ?1 ? 2 Dx2 C4 ? x1 C4 D B B

2

1

1. Both

and

are palindromes, .

! 



 §¤ 1

 e

g ? ? D D ! e gg g?  ? `1  B h 4 ? Y%¤1 B h 4  ? g

g

2G 1

are

g

a different -analogue of scattered-subwords appears in [2]. The notion of the alternate (signed) Parikh matrix developed in [6] has the nice property that the inverse of the matrix is the alternate Parikh of . This property also carries over to the matrix of the mirror image case of the Parikh -matrix mapping with some modi?cations. Let . We de?ne a morphism (called the alternate Parikh -matrix from to a collection of -dimensional upper-triangular mapping) matrices over . is de?ned on as follows: If , then 1. ,

2.

for

,

3.

if

,

4. all other entries of the matrix

are zero.

When the alphabet is

, then

Note that for

. As an example,

, we compute that

Suppose and . If and are the Parikh -matrix, and the alternate Parikh -matrix mappings from to upper-triangular integral matrices over , then the -dimensional matrix identity

holds.

!

. . .

..

.

. . .

h 4

Then the following result holds.

e ? ? ! ? g ?  ? ? g 

(7)



`

g  ?¤ ? ?¨ §??

D 4 ' 2 ED¨ D 4 ' 2 C ? p B ED \$1 B h 4



!

?

¤ ?g ? ?g

 



a ? ?" #

s v su g

¤ ?g ? ? DD g ?  ? q?" P7 C B 4 B h  ? g  ? gg g ?  Q"  g g ?  ?  c ? gQ" c  Q" 1  1 ? Y `1 ¤"  T g ??H D D ? D 8 D ? D Ut1 D  B H B Y B h 4 31 B h 4 h 4 Bh 4 h 4 Bh 4 g ? ? g ? ? ?EH D ? D ? D B h 4 G ! ey e ? g?  E B h 4 G ! ?? g ?  E31 B h 4 ?    e  e  ! 4  2  ?§¤?? ? ? g V ? ? ? ? x ?8\$?(?yw D \$1 B p 'p h 4 a v? ey ? ¨ X p ' uC ? g ? ? 7 G a 5 Q5?e ? 2 ' 2 C 7 p e ? p uC

?

?

s   ? v su g ? s   ? x su

?

D " B R T 4

? ?g ?¤¤ g ?

! ? f  'f t§¤ ? ?   ? ¨? ?

a

 

?

"

?

 g  



D B " P7

? qD" B D D P7 C B h 4 ?" B h 4

?

C

? ?g ?¤¤ ? h 4 4? ? 4    `h ! ? ? h   C? g
g

g g r¤f V ?? ? V ? ?h

g

?

4 ?

Proof Omitted.

It can also be shown that the identity (7) reduces to the matrix inverse identity of the Parikh matrix mapping of [6] when we extend the alphabet as in Theorem 9 and put .

References
[1] Atanasiu, A., Martin-Vide, C., Mateescu, A.: On the injectivity of the Parikh matrix mapping. Fundamenta Informaticae, 49 (2002) 289-299. [2] Egecioglu. O.: A -Matrix Encoding Extending the Parikh Matrix Mapping. Proc. Int. Conf. on Computers and Communications (ICCC 2004), Oradea, Romania, May, 2004. [3] Harju, T., Ibarra, O., Karhumaki, J., Salomaa, A: Some decision problems concerning semilinearity and commutation. J. Computer and System Sciences, 65 (2002), 278-294. [4] Ibarra, O.: Reversal-bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach., 24 (1978) 123-137. [5] Ibarra, O., Su, J., Dang, Z., Bultan, T., Kemmerer, R.: Counter machines and veri?cation problems. Theoretical Computer Science, 289 (2002) 165-189. [6] Mateescu, A., Salomaa, A., Salomaa K., Yu, S.: A sharpening of the Parikh mapping. Theoretical Informatics and Applications, 35 (2001) 551-564. [7] Parikh, R.J.: On context-free languages. J. Assoc. Comput. Mach., 13 (1966) 570-581. [8] Rozenberg, G., Salomaa, A. (eds): Handbook of Formal Languages. Springer, Berlin, 1997.
?

?

? e yg

A Matrix q-Analogue of the Parikh Map.pdf
A Matrix q-Analogue of the Parikh Map_专业资料。Abstract We introduce an extension of the Parikh mapping called the Parikh ￠-matrix mapping, which ...
A q-analogue of U(g[(N+1)), Hecke algebra, and the ....pdf
A q-analogue of U(g[(N+1)), Hecke algebra...a classical r matrix (= solution to the ...The map A (resp. A) endows 0 with a ...
...2004 A q-Matrix Encoding Extending the Parikh Ma....pdf
May, 2004 A q -Matrix Encoding Extending the Parikh Matrix Mapping ?mer ...glu, ?., and Ibarra, O.: A Matrix q-Analogue of the Parikh Map. ...
A q-analogue of Nahm's formalism for self-dual gaug....pdf
We present a q-analogue of Nahm's formalism for the BPS monopole, which...which is realized by multiplying v by a matrix g(x? ; q) on the right...
On the q-analogue of the hydrogen atom.pdf
The discrete spectrum of a q-analogue of the hydrogen atom is obtained ...Some trivial properties (matrix elements, timereversal behavior, adjointness ...
A q-analogue of Graf's addition formula for the Hah....pdf
A q-analogue of Graf's addition formula for the Hahn-Exton q-Bessel ...the interpretation of the Hahn-Exton q -Bessel function as matrix elements ...
A q-ANALOGUE OF GRAF'S ADDITION FORMULA FOR THE HAH....pdf
A q-ANALOGUE OF GRAF'S ADDITION FORMULA FOR THE HAHN-EXTON q-BESSEL ...the interpretation of the Hahn-Exton q-Bessel function as matrix elements ...
...Theory in Quantum Disc A q-Analogue of Berezin T....pdf
End(C[z]q,α ) be the covariant algebra of linear operators A : z j → m∈Z+ amj z m , j ∈ Z+ , with ?nitely many nonzero matrix ...
A q-analog of the Racah polynomials and the q-algeb....pdf
cients, i.e., a q-analogue of the Racah polynomials uα,β (x(s),...understood as the orthogonality property of the orthogonal matrix C = (Ctn ...
...of Quantum Density Matrix Using q-Boson Oscillat....pdf
Campus, Tharamani, Chennai- 600113, INDIA Abstract A q-analogue of Sudarshan’s diagonal representation of the Quantum Mechanical density matrix is obtained...
HAMA An Efficient Matrix Computation with the MapRe....pdf
This paper is a story about previous version of HAMA Only focus on matrix computation with MapReduce Shows simple case studies ? ? 4/19 The HAMA ...
A note on q-analogue of Sandor's functions.pdf
A note on q-analogue of Sandor's functions_专业资料。The additive analogues of Pseudo-Smarandache, Smarandache-simple functions and their duals have been ...
The q-deformed analogue of the Onsager algebra Beyo....pdf
The q?deformed analogue of the Onsager algebra: Beyond the Bethe ansatz approach...In these latter models, the transfer matrix can be decomposed on a ba...
...related to the Hamiltonicity of the Kneser.pdf
In Section 4 (see Theorem 1.6 below) we obtain a more precise ...1 if n 2k; k and from the q-analogue of the Erdos-Ko-Rado Theorem ...
A local form for the automorphisms of the spectral ....pdf
If F is an automorphism of ?n , the n2 -dimensional spectral unit ball, we show that, in a neighborhood of any cyclic matrix of ?n , the map ...
A q-ANALOGUE OF GRAF'S ADDITION FORMULA FOR THE HAH....pdf
A q-ANALOGUE OF GRAF'S ADDITION FORMULA FOR THE HAHN-EXTON q-BESSEL ...the interpretation of the Hahn-Exton q-Bessel function as matrix elements ...