# Property testing of Tree Regular Languages

date post

18-Jan-2016Category

## Documents

view

24download

2

Embed Size (px)

description

### Transcript of Property testing of Tree Regular Languages

Property testing of Tree Regular Languages Frdric Magniez, LRI, CNRSMichel de Rougemont, LRI , University Paris II

Property testing of Tree Regular Languages

Tester for regular words with the Edit Distance with Moves

2. Tester for ranked regular trees with the Tree-Edit Distance with Moves,

Testers on a class KLet F be a property on a class K of structures U

An -tester for F is a probabilistic algorithm A such that:If U |= F, A acceptsIf U is far from F, A rejects with high probability Time(A) independent of n.(Goldreich, Golwasser, Ron 1996 , Rubinfeld, Sudan 1994)

Tester usually implies a linear time corrector.

History of Testers Self-testers and correctors for Linear Algebra ,Blum & Kanan 1989

Robust characterizations of polynomials, R. Rubinfeld, M. Sudan, 1994

Testers for graph properties : k-colorability, Goldreich and al. 1996

graph properties have testers, Alon and al. 1999

Regular languages have testers, Alon and al. 2000s

Testers for Regular tree languages , Mdr and Magniez, ICALP 2004

Classical Edit Distance:Insertions, Deletions, Modifications

Edit Distance with moves0111000011110011001

01110111100000110013. Edit Distance with Moves generalizes to Trees

Edit distance on Words

Testers on words Simpler proof which generalizes to regular trees.L is a regular language and A an automaton for L.Admissible Z=

A word W is Z-feasible if there are two states initaccept

The Tester

For every admissible path Z: else REJECT. Theorem: Tester(W,A, ) is an -tester for L(A).Tester. Input : W,A,

Proof schema of the Tester Theorem: Regular words are testable.

Robustness lemma: If W is -far from L, then for every admissible path Z, there exists such that the number

of Z-infeasible subwords

Splitting lemma: if W is far from L there are many disjoint infeasible subwords.

Amplifying lemma: If there are many infeasible words, there are many short ones.

MergingMerging lemma: Let Z be an admissible path, and let F be a Z-feasible cut of size h . Then CCCCCCTake each word and split it along its connected components, removing single letters. Rearrange all the words of the same component in its Z-order.Add gluing words to obtain W in L:

Splitting

Splitting lemma: If Z is an admissible path, W a word s.t. dist(W,L) > h, then W hasProof by contraposition:

Tree-Edit-Distance

aebcdaebcaebcdfeDeletionEdgeInsertionNode andLabelTree Edit distance with moves:

aebcdaebcd1 moveDistance Problem is NP-complete, non-approximable.

Tree-Edit-Distance on binary treesBinary trees : Distance with moves allows permutations

Distance(T1,T2) =4 m-Distance (T1,T2) =2

Tree automata(q0, q0) q1(q0,q1) q1

q0q0q0q0q0q0q1q1q1q1q1q0q0q0q1q2(q1,q1)q2 (q1,q0)q2(q2,-) q2(-,q2) q2

Infeasible subtrees

Fact . If then the number of infeasible subtrees of constant size is O(n).

Tester for regular TreesTheorem: Tester(T,A, ) is an -tester for L(A).Tester. Input : T,A,

Proof schema of the Tester Theorem: Regular trees are testable.

Robustness lemma: If T is -far from L, then for every admissible path Z, there exists such that the number

of Z-infeasible i-subtrees

Splitting lemma: if T is far from L there are many disjoint infeasible subtrees.

Amplifying lemma: If there are many infeasible subtrees, there are many small ones.

Splitting and MergingCCCCCCSplitting and Merging on words:Splitting and Merging on trees:

Splitting and Merging trees

C D DCCEConnected ComponentsCorrected tree

ConclusionVerification is hard.Approximate verification can be feasible.

Testers and Correcters for regular wordsTester for regular treesCorrector for regular treesUnranked trees: XML filesApplications: Constant algorithm for Edit Distance with moves(Fischer, Magniez, Mdr)