BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nadia Ouali Sebti

Nadia Ouali Sebti appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata Theory

Catalog footprint

What is connected

3works
1topics
2close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

preprint2015arXiv

Algorithm for the k-Position Tree Automaton Construction

The word position automaton was introduced by Glushkov and McNaughton in the early 1960. This automaton is homogeneous and has (||\E||+1) states for a word expression of alphabetic width ||\E||. This kind of automata is extended to regular tree expressions. In this paper, we give an efficient algorithm that computes the \Follow sets, which are used in different algorithms of conversion of a regular expression into tree automata. In the following, we consider the k-position tree automaton construction. We prove that for a regular expression \E of a size |\E| and alphabetic width ||\E||, the \Follow sets can be computed in O(||\E||\cdot |\E|) time complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An Efficient Algorithm for the Equation Tree Automaton via the $k$-C-Continuations

Champarnaud and Ziadi, and Khorsi et al. show how to compute the equation automaton of word regular expression $E$ via the $k$-C-Continuations. Kuske and Meinecke extend the computation of the equation automaton to a regular tree expression $E$ over a ranked alphabet $Σ$ and produce a $O(R\cdot|E|^2)$ time and space complexity algorithm, where $R$ is the maximal rank of a symbol occurring in $Σ$ and $|E|$ is the size of $E$. In this paper, we give a full description of the algorithm based on the acyclic minimization of Revuz. Our algorithm, which is performed in an $O(|Q|\cdot|E|)$ time and space complexity, where $|Q|$ is the number of states of the produced automaton, is more efficient than the one obtained by Kuske and Meinecke.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

K-Position, Follow, Equation and K-C-Continuation Tree Automata Constructions

There exist several methods of computing an automaton recognizing the language denoted by a given regular expression: In the case of words, the position automaton P due to Glushkov, the c-continuation automaton C due to Champarnaud and Ziadi, the follow automaton F due to Ilie and Yu and the equation automaton E due to Antimirov. It has been shown that P and C are isomorphic and that E (resp. F) is a quotient of C (resp. of P). In this paper, we define from a given regular tree expression the k-position tree automaton P and the follow tree automaton F . Using the definition of the equation tree automaton E of Kuske and Meinecke and our previously defined k-C-continuation tree automaton C, we show that the previous morphic relations are still valid on tree expressions.

0 citations0 reviewsNo code linkedOpen access