Solving the weighted HOM-problem with the help of unambiguity
AT Nász - arXiv preprint arXiv:2309.02761, 2023 - arxiv.org
The HOM-problem, which asks whether the image of a regular tree language under a tree
homomorphism is again regular, is known to be decidable by [Godoy, Gim\'enez …
homomorphism is again regular, is known to be decidable by [Godoy, Gim\'enez …
Parameter reduction and automata evaluation for grammar-compressed trees
Trees can be conveniently compressed with linear straight-line context-free tree grammars.
Such grammars generalize straight-line context-free string grammars which are widely used …
Such grammars generalize straight-line context-free string grammars which are widely used …
Weighted tree automata with constraints
A Maletti, AT Nász - Theory of Computing Systems, 2024 - Springer
The HOM problem, which asks whether the image of a regular tree language under a given
tree homomorphism is again regular, is known to be decidable [Godoy & Giménez: The …
tree homomorphism is again regular, is known to be decidable [Godoy & Giménez: The …
Weighted HOM-problem for nonnegative integers
A Maletti, AT Nász, E Paul - arXiv preprint arXiv:2305.04117, 2023 - arxiv.org
The HOM-problem asks whether the image of a regular tree language under a given tree
homomorphism is again regular. It was recently shown to be decidable by Godoy, Gim\'enez …
homomorphism is again regular. It was recently shown to be decidable by Godoy, Gim\'enez …
Restricting Tree Grammars with Term Rewriting
J Bessai, L Czajka, F Laarmann… - … Conference on Formal …, 2022 - drops.dagstuhl.de
We investigate the problem of enumerating all terms generated by a tree-grammar which are
also in normal form with respect to a set of directed equations (rewriting relation). To this end …
also in normal form with respect to a set of directed equations (rewriting relation). To this end …
The HOM problem is EXPTIME-complete
C Creus, A Gascón, G Godoy… - 2012 27th Annual IEEE …, 2012 - ieeexplore.ieee.org
The HOM problem questions whether the image of a given regular tree language through a
given tree homomorphism is also regular. Decidability of HOM is an important theoretical …
given tree homomorphism is also regular. Decidability of HOM is an important theoretical …
Automata on infinite trees with equality and disequality constraints between siblings
This article is inspired by two works from the early 90s. The first one is by Bogaert and Tison
who considered a model of automata on finite ranked trees where one can check equality …
who considered a model of automata on finite ranked trees where one can check equality …
Dyna 2: Towards a general weighted logic language
NW Filardo - 2017 - jscholarship.library.jhu.edu
We investigate the design of an expressive, purely-declarative, weighted logic programming
language, Dyna. Dyna is a decade-plus effort in pushing the boundaries of declarative …
language, Dyna. Dyna is a decade-plus effort in pushing the boundaries of declarative …
Bottom-up tree automata with term constraints
A Reuß, H Seidl - International Conference on Logic for Programming …, 2010 - Springer
We introduce bottom-up tree automata with equality and disequality term constraints. These
constraints are more expressive than the equality and disequality constraints between …
constraints are more expressive than the equality and disequality constraints between …
The Weighted HOM-Problem Over Fields
AT Nász - International Conference on Current Trends in Theory …, 2024 - Springer
The HOM-problem, which asks whether the image of a regular tree language under a tree
homomorphism is again regular, is known to be decidable. In this paper, we prove the …
homomorphism is again regular, is known to be decidable. In this paper, we prove the …