Zobrazeno 1 - 10
of 3 379
pro vyhledávání: '"Tree languages"'
Publikováno v:
In Information and Computation December 2024 301 Part B
Autor:
Blumensath, Achim
We study the question of whether a given regular language of finite trees can be defined in first-order logic. We develop an algebraic approach to address this question and we use it to derive several necessary and sufficient conditions for definabil
Externí odkaz:
http://arxiv.org/abs/2407.01169
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the
Externí odkaz:
http://arxiv.org/abs/2307.10131
Autor:
Julaluk Boonsol1 julaluk.bs@kkumail.com, Pongsakorn Kitpratyakul1 pongsakorn.k@kkumail.com, Thawhat Changphas1 thacha@kku.ac.th, Bundit Pibaljommee1 banpib@kku.ac.th
Publikováno v:
International Journal of Mathematics & Computer Science. 2024, Vol. 19 Issue 2, p279-288. 10p.
Autor:
Berglund, Martin1 (AUTHOR) mbe@cs.umu.se, Björklund, Henrik1 (AUTHOR), Björklund, Johanna1 (AUTHOR) mbe@cs.umu.se
Publikováno v:
Algorithms. Jun2024, Vol. 17 Issue 6, p268. 14p.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Bartholdi, Laurent, Noce, Marialaura
We study the portraits of isometries of rooted trees - the labelling of the tree, at each vertex, by the permutation of its descendants - in terms of languages. We characterize regularly branched self-similar groups in terms of $\omega$-regular langu
Externí odkaz:
http://arxiv.org/abs/2203.12963
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Leupold, Peter, Maneth, Sebastian
It is well known that for a regular tree language it is decidable whether or not it can be recognized by a deterministic top-down tree automaton (DTA). However, the computational complexity of this problem has not been studied. We show that for a giv
Externí odkaz:
http://arxiv.org/abs/2107.03174