advertisement

Framed vs Unframed Two-dimensional languages Marcella Anselmo Natasha Jonoska Maria Madonia Univ. of Salerno Univ. South Florida Univ. of Catania ITALY USA ITALY Two-dimensional (2dim) languages In the literature two kinds of 2dim languages • Sets of finite pictures Ex. L01= the set of finite pictures with one occurrence of symbol “1” at most and symbol “0” in the other positions 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 • Tilings of the infinite plane Ex. Tiling of the infinite plane with one occurrence of symbol “1” at most and symbol “0” in the other positions 0 0 0 0 0 0 1 0 0 0 0 0 Remark: The set of its finite blocks is L01 0 0 0 0 0 0 0 0 0 0 0 0 Overview of the talk • Topic: Recognizable 2dim languages • Motivation: In the literature recognizable = (symbol-to-symbol) projection of local with two different approaches framed for finite pictures and unframed for the infinite plan In this talk New “unframed” definition for “finite” pictures • Results of comparison framed vs unframed with special focus on determinism and unambiguity M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Local 2dim languages “Framed” approach • Generalization of local 1dim (string) languages • sharp () is needed to test locality conditions on the boundaries a a a a a a a a 1 1 1 1 b b b b “Unframed” approach • Tiling of the (infinite) plane • No sharp is needed! a a a a a a a a 1 1 1 1 b b b b 0 0 0 0 0 0 1 0 0 0 0 0 Local languages: LOC • finite alphabet, ** all pictures over , L ** 2dim language • To define local languages, identify the boundary of a picture p using a boundary symbol p= p= • L is local if there exists a finite set of tiles (i. e. square pictures of size 22) such that, for any p in L, any subpicture 22 of p is in (and we write L=L() ) M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Example of local language Ld = the set of square pictures with symbol “1” in all main diagonal positions and symbol “0” in the other positions = 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 M. Anselmo N. Jonoska M. Madonia 1 0 0 p= 0 1 0 0 0 1 # # p= # # # # 1 0 0 # # 0 1 0 # # 0 0 1 # # # # # # Framed vs Unframed 2dim languages Recognizable languages: REC • L is recognizable by tiling system if L= (L’) where L’ is a local language and is a mapping from the alphabet of L’ to the alphabet of L • (, , , ) , where L’=L(), is called tiling system • REC is the family of two-dimensional languages recognizable by tiling system [Giammarresi, Restivo 91] Example: LSq = all squares over {a} is recognizable by tiling system. Set L’=Ld and (1)= (0)= a M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Factorial local/recognizable languages • Factorial recognizable languages (FREC) are defined in terms of factorial local languages (FLOC) Do not care about the boundary of a picture! • L is factorial local if there exists a finite set of tiles (i. e. square pictures of size 22) such that, for any p in L, any sub-picture 22 of p is in (and we write L=Lu() ) (throw away the … hat!!!) • L is factorial tiling recognizable if L= (L’) where L’ is a factorial local language and is a mapping from the alphabet of L’ to the alphabet of L (, , , ) , where L’=Lu(), is called unbordered tiling system M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Example of L in FREC L01 = the set of pictures with one occurrence of symbol “1” at most and symbol “0” in the other positions 0 0 0 0 0 0 0 0 1 0 h 0 0 0 0 0 d h 0 0 0 0 0 d h 0 0 0 0 0 e e e c f a a a 1 b g g g d g g g g g g = e e e e e c e c c f c f f f f f e e a a e c a 1 c f 1 b f f b b a a g g a 1 g d 1 b d h b b h h g g g g g d g d d h d h h h h h M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages LOC and FLOC, REC and FREC • L FLOC or L FREC implies L factor-closed (i.e. L=F(L) where F(L) is the set of all factors of L) • L FLOC implies L LOC (adding everywhere) • L FREC (as before) implies L REC • FLOC / LOC Example: Ld LOC, not factor-closed • FREC / REC (as before) M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Characterization of FLOC inside LOC and of FREC inside REC Proposition FLOC = LOC Factor-closed Proof LLOC and L factor-closed implies L FLOC. Indeed (remove tiles with ) no for F(L)=L Proposition L FREC iff L REC and L=(K) with K factor-closed local language M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Determinism and unambiguity • “Computing” by a tiling system (, , , ) Given a picture p** looking for p’ ** such that (p’)=p (i.e. for a pre-image p’ of p) • Determinism One possible next step • Unambiguity One possible accepting computation Remark Usually Determinism implies Unambiguity M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Determinism in REC: DREC Def. [A, Giammarresi, M 07] A tiling system is tl-brdeterministic if a,b,c and s , unique tile a b c d such that (d)=s. s unique way to fill this position with a symbol of whose projection matches symbol s (Analogously tr-bl,bl-tr,br-tl -deterministic tiling system) DREC languages that admit a tl-br or tr-bl or bl-tr or br-tldeterministic tiling system M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Unambiguity in REC: UREC Definition [Giammarresi,Restivo 92] A tiling system (, , , ) is unambiguous for L ** if for any pL there is a unique p’ L’ such that (p’)=p (p’ pre-image of p). L ** is unambiguous if it admits an unambiguous tiling system. UREC = all unambiguous recognizable 2dim languages Proposition [A, Giammarresi, M 07] LOC / DREC / UREC / REC M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Ambiguity in REC Definition L ** is finitely-ambiguous if there exists a tiling system for L such that every picture pL has k pre-images at most (for some k >1). L is infinitely-ambiguous if it is not finitely ambiguous. M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Determinism and unambiguity in FREC • DFREC = languages that admit a deterministic unbordered tiling system • UFREC = languages that admit an unambiguous unbordered tiling system • Finitely-ambiguous and infinitely ambiguous factorial recognizable languages M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Example Recall the example L01 p= e e e c f a a a 1 b 0 g g g d h 0 0 g g g d h 0 0 g g g d h 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 The unbordered tiling system for L01 is deterministic but it is not unambiguous M. Anselmo N. Jonoska M. Madonia -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 g g g d g g g d g g g d g g d h g g d h g g d h Framed vs Unframed 2dim languages Example (continued) p= e e e c f a a a 1 b 0 g g g d h 0 0 g g g d h 0 0 g g g d h 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 -1 Moreover it can be shown that L01 is an infinitely ambiguous factorial language. M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Unambiguity in FREC Proposition. UFREC = FLOC Proof. If L FLOC then is the identity. If L UFREC any symbol in has an unique pre-image and then is a one-to-one mapping Remarks. • UFREC is a very limited notion • DFREC does not imply UFREC A better suited definition of unambiguity is necessary M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Frame-unambiguity (I) Definition An unbordered tiling system for L is frame-unambiguos at p L if, once we fix a frame of local symbols in p, p has at most one pre-image. p= One pre-image at most Definition LFREC is frame-unambiguous if it admits a frame-unambiguous unbordered tiling system. Remark The frame of boundary symbols in UREC is replaced by a frame of local symbols M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Frame unambiguity (II) In L01 p= g0 g0 0 g 0 d g0 0 0 g0 g0 0 g 0 0 0 0 0 e e e c f 0 0 0 1 0 a a a 1 b 0 0 0 0 0 g g g d h 0 0 0 0 0 g g g d h 0 0 0 0 0 g g g d h -1 g g g d 0 d g g g d 0 d g g g d -1 L01 is frame-unambiguous Proposition L DFREC implies L is frame-unambiguous M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Ambiguity in REC vs ambiguity in FREC (I) In REC In FREC Determinism Determinism Unambiguity Frame-Unambiguity Unambiguity There are languages There are languages • infinitely ambiguous • infinitely ambiguous • unambiguous • finitely-ambiguous • unambiguous (as far as we know) M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Ambiguity in REC vs ambiguity in FREC (II) Remark Frame reduces the ambiguity degree • Finitely-ambiguous factorial in FREC and unambiguous in REC 0a 0a 1 0 b 0 0 0a 0a 1 0 b 0 0 -1 a a a a b b b b 0a 0a 1 b 0 0a 0a 0a 0a 1 b 0 0a 0a M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Ambiguity in REC vs ambiguity in FREC (III) Moreover • Infinitely factorial ambiguous in FREC and unambiguous in REC 0e 0e 0c 0f 0a 0a 1 b 0 0g g 0 d 0 h 0 M. Anselmo N. Jonoska M. Madonia 0e 0e 0e 0e 0e 0e Framed vs Unframed 2dim languages Conclusions • Frame can enforce size and content of recognized pictures • Frame can reduce ambiguity degree Additional memory Factorial recognizable 2dim symbolic dynamical systems analogies and interpretations in symbolic dynamics M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Grazie Conclusions Frame can enforce size and content of recognized pictures Frame can reduce ambiguity degree Additional memory Tilings of the plane 2dim symbolic dynamical systems analogies and interpretations in symbolic dynamics Note When sets of tilings are invariant under translations, in symbolic dynamics: Local “shifts of finite type” Projection “sofic shifts” M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Decidability properties Proposition: It is decidable whether a given unbordered tiling system is unambiguous and whether it is deterministic. Proposition: It is undecidable whether a given unbordered tiling system is frame-unambiguous. M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Removing tiles with # does not always work … • Given a tiling system for L REC, this does not allow to recognize F(L) as element of FREC Example Consider Ld and the tiling system for it. Teta contains all the sub-tiles of # # # # # # 1 0 0 # # 0 1 0 # # 0 0 1 # # # # # # 0 0 1 0 0 1 0 0 T no but 0 0 1 1 0 0 F(L) • Given a tiling system for L=F(L) REC, we cannot prove that this allow to recognize L as subset of FREC M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Finite and infinite ambiguity in FREC Proposition: For any k >=1, there is a k-factorialambiguous language. Proposition: Unambiguous-FREC (Col-UFREC RowUFREC) Finitely ambiguous FREC TOGLIERE? SI Proposition: (Col-UFREC Row-UFREC) DFREC Frame-unambiguous FREC M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages Two-dimensional Languages Picture or two-dimensional string over a finite alphabet: a b b c a c b a c b b a a b a • finite alphabet • ** all 2dim rectangular words (pictures) over • L ** 2dim language Local 2dim languages: first approach First approach (“framed” one) Generalization of local 1dim (string) languages 1dim: L= an1bm | n,m>0 a a a 1 b b a a a a 1 2dim: a a a a a a a a 1 1 1 1 b b b b 1 b b b b a a a a a a a a 1 1 1 1 is finite b b b b Unambiguity in FREC (II) One pre-image UFREC Fix no local symbol Fix first column or first row of local symbols Fix two consecutive sides of local symbols DFREC Fix the frame New definition M. Anselmo N. Jonoska M. Madonia Framed vs Unframed 2dim languages