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 Hcfebdcba`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 F4 Y B ? U4 31 QF4 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  QF4 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?P5 ¨ 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  HcfebdY 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
?

 D1 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¨ qDDg 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

? cfebdY 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 ? ? SS 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 ? SS 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  01 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 cfebdY 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 ...
q-ANALOGUES OF EULER'SODD=DISTINCT THEOREM.pdf
1. The ?rst q-analogue of Euler’s Odd=Distinct theorem uses 1 ? qn ...For Theorem 2 the Glaisher map replaces each part {2k o}q by 2k To (...
A q-Matrix Encoding Extending the Parikh Matrix Mapping.pdf
Keywords: Parikh mapping, Parikh matrix mapping, scattered subword, q-analogue. 1 Introduction By Parikh’s theorem [7], the commutative image of any ...
...A q-Matrix Encoding Extending the Parikh Matrix Mapping_....pdf
Keywords: Parikh mapping, Parikh matrix mapping, scattered subword, q -analogue. 1 Introduction By Parikh’s theorem [7], the commutative image of any ...
q-ANALOGUE OF WILSON’S THEOREM.pdf
q-ANALOGUE OF WILSON’S THEOREM_专业资料。...the automorphism of Q(ζ) mapping ζ to ζ s... Determinants of Legendre symbol matrices, Acta ...
A q-analogue of U(g[(N+1)), Hecke algebra, and the Yang-....pdf
A q-analogue of U(g[(N+1)), Hecke algebra...The map A (resp. A) endows 0 with a ...in (1) the Cartan matrix ofA ~ [6, 8], ...
A q -analogue of an identity of N. Wallach.pdf
是有关组合数学中q-analogue的研究内容,属最新资料。 A q-analogue of an ...[PH] R. M. Phatarfod, On the matrix occuring in a linear search ...
A q-analogue of Graf's addition formula for the Hahn-Exton q-....pdf
We start the proof of the q -analogue of Graf’s addition formula (1.4) for the Hahn-Exton q -Bessel function by proving the product formula (1.5)...
A q -Analogue of the Path Length of Binary Search Trees.pdf
A q -Analogue of the Path Length of Binary Search Trees_理学_高等教育_教育专区。是有关组合数学中q-analogue的研究内容,属最新资料。 ...
ON THE SUM FORMULA FOR THE q-ANALOGUE OF NON-STRICT MULTIPLE ....pdf
ON THE SUM FORMULA FOR THE q-ANALOGUE OF NON-STRICT MULTIPLE ZETA VALUES_专业资料。Abstract. In this article, the q-analogues of the linear relations ...
Applications of q-Taylor theorems.pdf
1 k = (1 ? 2ax + a2 )k we can consider k (x; a) as a q -analogue of (x ? c)k for c = a + 1=a. The Taylor theorem for k (x...
An analog of the Fourier transformation for a q-harmonic ....pdf
An analog of the Fourier transformation for a q-harmonic oscillator_专业资料。A q-version of the Fourier transformation and some of its properties are ...
A note on the sums of powers of consecutive q-integers.pdf
As a response to Garrett and Hummel’s question, Warnaar gave a simple q-analogue of the sum of cubes as follows: n q k=1 2n?2k 1 ? qk 2 2...
q-Analogue of $A_{m-1}oplus A_{n-1}subset A_{mn-1}$.pdf
q-Analogue of $A_{m-1}oplus A_{n-1}...1 algebras the explicit form of the R -matrix ...). An example of such a mapping from su(2) ...
...ZEROS OF LAGUERRE POLYNOMIALS AND THEIR q-ANALOGUES.pdf
In general, the polynomials give a q-analogue of the Jacobi polynomials but, for b < 0, they give a q-analogue of the Laguerre polynomials; see (...
The Descent Set and Connectivity Set of a Permutation.pdf
a matrix that records the joint distribution of ...maps f : P → {1, 2, . . .} and xf =...The q-analogue will keep track of the number ...
Combinatorial interpretations of the q-Faulhaber and q-Salié....pdf
s formula for the sums of powers and a q -analogue of Gessel-Viennot’...2. Inverses of matrices Recall that the n-th complete homogeneous functions...
I A.pdf
In conclusion, we raise the question as to whether there is a q-analogue of formula (1), (q) i.e., for the (0,1)-inclusion matrix Wt,k (v...
A characterization of hypergraphs which are products of a ....pdf
(V , E ), is a bijective map f : V → V such that (k ? V ) ...[12] P.V. Ceccherini: A q-analogue of the characterization of ...
The traces of quantum powers commute.pdf
The traces of the quantum powers of a generic quantum matrix pairwise ...(a q -analogue of the adjoint action) of GLq (n) on O(Mq ); in ...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图