| Issue |
RAIRO-Theor. Inf. Appl.
Volume 55, 2021
11th Workshop on Non-classical Models of Automata and Applications (NCMA 2019)
|
|
|---|---|---|
| Article Number | 4 | |
| Number of page(s) | 21 | |
| DOI | https://doi.org/10.1051/ita/2021008 | |
| Published online | 22 July 2021 | |
Bottom-Up derivatives of tree expressions
1
USTHB, Faculty of Mathematics, RECITS Laboratory, BP 32, El Alia,
16111
Bab Ezzouar,
Algiers, Algeria.
2
Groupe de Recherche Rouennais en Informatique Fondamentale, Université de Rouen Normandie, Avenue de l’Université,
76801
Saint-Étienne-du-Rouvray, France.
3
Associated Member of RECITS Laboratory, CATI Team, USTHB,
Algiers, Algeria.
* Corresponding author: sattou@usthb.dz
Received:
17
December
2019
Accepted:
26
May
2021
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.
Mathematics Subject Classification: 68Q45
Key words: Regular tree expressions / derivatives tree automata / partial derivatives / bottom-Up derivatives
© The authors. Published by EDP Sciences, 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.