Zobrazeno 1 - 10
of 24
pro vyhledávání: '"Tree Homomorphism"'
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:
Gustav Grabolle
Publikováno v:
GandALF
This paper connects the classes of weighted alternating finite automata (WAFA), weighted finite tree automata (WFTA), and polynomial automata (PA). First, we investigate the use of trees in the run semantics for weighted alternating automata and prov
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e4ac91d5d6d6440598dbc54919276654
Publikováno v:
Developments in Language Theory ISBN: 9783030815073
DLT
DLT
We prove that for a given deterministic top-down transducer with look-ahead it is decidable whether or not its translation is definable (1) by a linear top-down tree transducer or (2) by a tree homomorphism. We present algorithms that construct equiv
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::17eb5e625c0e9a86dbda1f252f764452
https://doi.org/10.1007/978-3-030-81508-0_24
https://doi.org/10.1007/978-3-030-81508-0_24
Conference
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:
Omer Giménez, Guillem Godoy
Publikováno v:
Journal of the ACM. 60:1-44
We close affirmatively a question that has been open for long time: decidability of the HOM problem. The HOM problem consists in determining, given a tree homomorphism H and a regular tree language L represented by a tree automaton, whether H ( L ) i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a8b743ca80542f2205e188a26e6b9ea5
https://doi.org/10.1145/2508028.2501600
https://doi.org/10.1145/2508028.2501600
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783319299990
LATA
LATA
We prove that the class of linear context-free tree languages is not closed under inverse linear tree homomorphisms. The proof is by contradiction: we encode Dyck words into a context-free tree language and prove that its preimage under a certain lin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b387d00eafca9bfc482348f57c9fd25c
https://doi.org/10.1007/978-3-319-30000-9_37
https://doi.org/10.1007/978-3-319-30000-9_37
Publikováno v:
Fundamenta Informaticae. 111:163-202
Weighted extended tree transducers (wxtts) over countably complete semirings are systematically explored. It is proved that the extension in the left-hand sides of a wxtt can be simulated by the inverse of a linear and nondeleting tree homomorphism.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8448f0236c0fd9db1ae0aaec3bad4bc1
https://doi.org/10.3233/fi-2011-559
https://doi.org/10.3233/fi-2011-559
We prove that the class of linear context-free tree languages is not closed under inverse linear tree homomorphisms. The proof is by contradiction: we encode Dyck words into a context-free tree language and prove that its preimage under a certain lin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::389ea534e674543847b50d2300736c55
http://arxiv.org/abs/1510.04881
http://arxiv.org/abs/1510.04881
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
Universitat Jaume I
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
Universitat Jaume I
A constrained term pattern s:@f represents the language of all instances of the term s satisfying the constraint @f. For each variable in s, this constraint specifies the language of its allowed substitutions. Regularity of languages represented by s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37c9854f73c791f1b90e14e272565c16
https://hdl.handle.net/2117/23504
https://hdl.handle.net/2117/23504
Autor:
Helmut Seidl, Andreas Reuß
Publikováno v:
Implementation and Application of Automata ISBN: 9783642316050
CIAA
CIAA
We extend ${\mathcal H}_1$-clauses with disequalities between images of terms under a tree homomorphism (hom-disequalities). This extension allows to test whether two terms are distinct modulo a semantic interpretation, allowing, e.g., to neglect inf
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c913e47ca82d72afd05c70222a0054a8
https://doi.org/10.1007/978-3-642-31606-7_26
https://doi.org/10.1007/978-3-642-31606-7_26