Bottom-Up Derivatives of Tree Expressions
RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 4

In this paper, we extend the notion of (word) derivatives and partial derivatives due to (respectively) Brzozowski and Antimirov to tree derivatives using already known inductive formulae of quotients. We define a new family of extended regular tree expressions (using negation or intersection operators), and we show how to compute a Brzozowski-like inductive tree automaton; the fixed point of this construction, when it exists, is the derivative tree automaton. Such a deterministic tree automaton can be used to solve the membership test efficiently: the whole structure is not necessarily computed, and the derivative computations can be performed in parallel. We also show how to solve the membership test using our (Bottom-Up) partial derivatives, without computing an automaton.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2021008
Classification : 68Q45
Keywords: Regular tree expressions, derivatives tree automata, partial derivatives, bottom-up derivatives 
@article{ITA_2021__55_1_A6_0,
     author = {Attou, Samira and Mignot, Ludovic and Ziadi, Djelloul},
     editor = {Holzer, Markus and Sempere, Jos\'e M.},
     title = {Bottom-Up {Derivatives} of {Tree} {Expressions}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ita/2021008},
     mrnumber = {4289539},
     zbl = {1508.68183},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2021008/}
}
TY  - JOUR
AU  - Attou, Samira
AU  - Mignot, Ludovic
AU  - Ziadi, Djelloul
ED  - Holzer, Markus
ED  - Sempere, José M.
TI  - Bottom-Up Derivatives of Tree Expressions
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2021
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2021008/
DO  - 10.1051/ita/2021008
LA  - en
ID  - ITA_2021__55_1_A6_0
ER  - 
%0 Journal Article
%A Attou, Samira
%A Mignot, Ludovic
%A Ziadi, Djelloul
%E Holzer, Markus
%E Sempere, José M.
%T Bottom-Up Derivatives of Tree Expressions
%J RAIRO. Theoretical Informatics and Applications
%D 2021
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2021008/
%R 10.1051/ita/2021008
%G en
%F ITA_2021__55_1_A6_0
Attou, Samira; Mignot, Ludovic; Ziadi, Djelloul. Bottom-Up Derivatives of Tree Expressions. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 4. doi: 10.1051/ita/2021008

[1] V. M. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155 (1996) 291–319. | MR | Zbl | DOI

[2] S. Attou, L. Mignot and D. Ziadi, Extended tree expressions and their derivatives, in NCMA, Valencia, Spain, July 2–3, 2019 (2019) 47–62.

[3] J. A. Brzozowski, Derivatives of regular expressions. J. ACM 11 (1964) 481–494. | MR | Zbl | DOI

[4] P. Caron, J. Champarnaud and L. Mignot, Partial derivatives of an extended regular expression, in LATA, vol. 6638 of Lecture Notes in Computer Science. Springer (2011) 179–191. | Zbl | DOI

[5] P. Caron, J. Champarnaud and L. Mignot, A general framework for the derivation of regular expressions. RAIRO - Theor. Inf. Appl. 48 (2014) 281–305. | MR | Zbl | Numdam | DOI

[6] J.-M. Champarnaud, L. Mignot, N. O. Sebti and D. Ziadi, Bottom-up quotients for tree languages. J. Autom. Lang. Combinat. 22 (2017) 243–269. | MR | Zbl

[7] G. P. Huet, The zipper. J. Funct. Program. 7 (1997) 549–554. | MR | Zbl | DOI

[8] S. Kleene, Representation of events in nerve nets and finite automata. Automata Studies, Ann. Math. Stud. 34 (1956) 3–41. | MR

[9] D. Kuske and I. Meinecke, Construction of tree automata from regular expressions. RAIRO – Theor. Inf. Appl. 45 (2011) 347–370. | MR | Zbl | Numdam | DOI

[10] É. Laugerotte, J.-G. Luque, L. Mignot and F. Nicart, Multilinear representations of free pros. Linear Multilinear Algeb. (2019) 1–45. | MR | Zbl

[11] L. Mignot, Application: Bottom up derivatives. http://ludovicmignot.free.fr/programmes/BottomUpPartialDerivatives/index.html. Accessed: 2019-12-08.

[12] J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2 (1968) 57–81. | MR | Zbl | DOI

Cité par Sources :