Report

Two-dimensional Rational Automata: a bridge unifying 1d and 2d language theory Marcella Anselmo Univ. of Salerno Dora Giammarresi Maria Madonia Univ. Roma Tor Vergata Univ. of Catania ITALY Overview • Topic: recognizability of 2d languages • Motivation: putting in a uniform setting concepts and results till now presented for 2d recognizable languages • Results: definition of rational automata. They provide a uniform setting and allow to obtain results in 2d just using techniques and results in 1d Two-dimensional (2d) languages Two-dimensional string (or picture) over a finite alphabet: a b b c c b a a b a a b • finite alphabet • ** pictures over • L ** 2d language Problem: generalizing the theory of recognizability of formal languages from 1d to 2d 2d literature Since ’60 several attempts and different models • 4NFA, OTA, Grammars, Tiling Automata, Wang Automata, Logic, Operations Most accreditated generalization: REC family REC family I • REC family is defined in terms of 2d local languages • It is necessary to identify the boundary of picture p using a boundary symbol p= p= • A 2d language L is local if there exists a 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 REC family II • L ** is recognizable by tiling system if L = (L’) where L’ G** is a local language and is a mapping from the alphabet G of L’ to the alphabet of L • (, G, , ) is called tiling system • REC is the family of two-dimensional languages recognizable by tiling system Example Consider Lsq the set of all squares over = {a} • Lsq is not local. Lsq is recognizable by tiling system. • Lsq = (L’) where L’ is a local language over G = {0,1,2} and is such that (0)=(1)=(2)=a p= 1 0 0 0 2 1 2 2 0 0 1 0 2 2 2 1 L’ (p) = a a a a a a a a a a a a a a a a Lsq Why another model? REC family has been deeply studied • Notions: unambiguity, determinism … • Results: equivalences, inclusions, closure properties, decidability properties … but … ad hoc definitions and techniques From 1d to 2d This new model of recognition gives: • a more natural generalization from 1d to 2d • a uniform setting for all notions, results, techniques presented in the 2d literature Starting from Finite Automata for strings we introduce Rational Automata for pictures In this setting • Some notions become more «natural» (e.g. different forms of determinism) • Some techniques can be exported from 1d to 2d (e.g. closure properties) • Some results can be exported from 1d to 2d (e.g. classical results on transducers) From Finite Automata to Rational Automata We take inspiration from the geometry: Points Symbols 1d 1d Lines Strings 2d 2d Planes Pictures • Finite sets of symbols are used to define finite automata that accept rational sets of strings • Rational sets of strings are used to define rational automata that accept recognizable sets of pictures From Finite Automata to Rational Automata Finite Automaton A = (, Q, q0, d, F) finite set of symbols Q finite set of states q0 initial state d finite relation on (Q X ) X 2Q F finite set of final states Symbol String Finite Rational Rational Automaton!! Rational Automata (RA) A = (, Q, q0, d, F) finite set of symbols Q finite set of states q0 initial state d finite relation on (Q X ) X 2Q F finite set of final states Symbol String Finite Rational Rational automaton H = (A, SQ, S0, dT, FQ) A = + rational set of strings on SQ Q+ rational set of states S0 = q0+ initial states dT rational relation on (SQ X A) X 2SQ computed by transducer T FQ rational set of final states Rational Automata (RA) ctd. RA H = (A, SQ, S0, dT, FQ) dT rational relation on (SQ X A) X 2SQ What does it mean??? computed by transducer T SQ Q+ A = + If s = s1 s2 … sm SQ and a = a1 a2 … am A then q = q1 q2 … qm dT (s , a) if q is output of the transducer T on the string (s1,a1) (s2,a2) … (sm,am) over the alphabet Q X Recognition by RA A computation of a RA on a picture p ++, p of size (m,n), is done as in a FA, just considering p as a string over the alphabet of the columns A = + i.e. p = p1 p2 … pn with pi A Example: a a a a a a a a a a a a a a a a a a a a a a a a p1 p2 p3 p4 picture a a a a ++ a a a p a string Recognition by RA (ctd.) The computation of a RA H on a picture p, of size (m,n), starts from q0m, initial state, and reads p, as a string, column by column, from left to right. FQ is rational p is recognized by H if, at the end of the computation, a state qf FQ is reached. L(H) = language recognized by H L(RA) = class of languages recognized by RA Example 1 RA recognizing Lsq set of all squares over = {a} Let Q = {q0,0,1,2} and Hsq = ( A, SQ, S0, dT, FQ) with A = a+ , SQ = q0+ 0*12* Q+ , S0 = q0+ , FQ = 0*1, dT computed by the transducer T T L(Hsq) = Lsq Example 1:computation a a a a Computation on p = T a a a a a a a a a a a a dT (q04, a4) = output of T on (q0,a) (q0,a) (q0,a) (q0,a) = 1222 dT (1222, a4) = 0122 dT (0122, a4) = 0012 dT (0012, a4) = 0001 FQ p L(Hsq)=Lsq RA and REC This example gives the intuition for the following Theorem A picture language is recognized by a Rational Automaton iff it is tiling recognizable Remark This theorem is a 2d version of a classical (string) theorem Medvedev ’64: Theorem A string language is recognized by a Finite Automaton iff it is the projection of a local language Furthermore In the previous example the rational automaton Hsq mimics a tiling system for Lsq but … in general the rational automata can exploit the extra memory of the states of the transducers as in the following example. Example 2 Consider Lfr=fc the set of all squares over = {a,b} with the first row equal to the first column. • Lfr=fc L(RA) • The transition function is realized by a transducer with states r0, r1, r2, ry, dy for any y Similarity with other models • Rational Graphs • Iteration of Rational Transducers • Matz’s Automata for L(m) Studying REC by RA • Closure properties • Determinism: definitions and results • Decidability results Closure properties Proposition L(RA) is closed under union, intersection, column- and row-concatenation and stars. Proof The closure under row-concatenation follows by properties of transducers. The other ones can be proved by exporting FA techniques. Determinism in REC The definition of determinism in REC is still controversial Different definitions The “right” one? Different classes: DREC, Col-Urec, Snake-Drec Now, in the RA context, all of them assume a natural position in a common setting with nondeterminism and unambiguity Determinism: definition Two different definitions of determinism can be given 1. The transduction is a function (i.e. dT on (SQ X A) X SQ) Deterministic Rational Automaton (DRA) 2. The transduction is left-sequential Strongly Deterministic Rational Automaton (SDRA) Col-UREC DREC Determinism: results Theorem L is in L(DRA) iff L is in Col-UREC L is in L(SDRA) iff L is in DREC Remark It was proved Col-UREC=Snake-Drec with ad hoc techniques Lonati&Pradella2004. In the RA context Col-UREC=Snake-Drec follows easily by a classical result on transducers Elgot&Mezei1965 Decidability results Proposition It is decidable whether a RA is deterministic (strongly deterministic, resp.) Proof It follows very easily from decidability results on transducers. Conclusions Despite a rational automaton is in principle more complicated than a tiling system, it has some major advantages: • It unifies concepts coming from different motivations • It allows to use results of the string language theory Further steps: look for other results on transducers and finite automata to prove new properties of REC. Grazie per l’attenzione!