Zoltán Fülöp

I&C Journal 2024 Journal Article

Rational weighted tree languages with storage

• Frederic Dörband
• Zoltán Fülöp
• Heiko Vogler

We define the class of rational weighted tree languages with storage over complete, not necessarily commutative, semirings and we repeat its characterization by weighted regular tree grammars with storage. Moreover, we show an alternative proof of the fact that the class of rational weighted tree languages with storage is closed under the rational operations, i. e. , top-concatenation, scalar multiplication, sum, tree concatenation, and Kleene-star, where the latter two closure results require that the storage has a reset instruction.

TCS Journal 2022 Journal Article

Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids

• Manfred Droste
• Zoltán Fülöp
• Dávid Kószó
• Heiko Vogler

We consider weighted tree automata over strong bimonoids (for short: wta). A wta A has the finite-image property if its recognized weighted tree language 〚 A 〛 has finite image; moreover, A has the preimage property if the preimage under 〚 A 〛 of each element of the underlying strong bimonoid is a recognizable tree language. For each wta A over a past-finite monotonic strong bimonoid we prove the following results. In terms of A 's structural properties, we characterize whether it has the finite-image property. We characterize those past-finite monotonic strong bimonoids such that for each wta A it is decidable whether A has the finite-image property. In particular, the finite-image property is decidable for wta over past-finite monotonic semirings. Moreover, we prove that A has the preimage property. All our results also hold for weighted string automata.

I&C Journal 2022 Journal Article

Principal abstract families of weighted tree languages

• Zoltán Fülöp
• Heiko Vogler

We introduce semiring-weighted regular tree grammars with storage where the semiring is complete. We show that the class of weighted tree languages generated by them is a principal abstract family of weighted tree languages provided that the semiring is commutative, the rank of symbols occurring in trees is bounded by a global parameter, and that the storage is finitely encoded and contains a reset instruction. Moreover, we prove the same statement for the iterated pushdown (instead of finitely encoded storage containing a reset instruction).

I&C Journal 2019 Journal Article

A Kleene theorem for weighted tree automata over tree valuation monoids

• Doreen Götze
• Zoltán Fülöp
• Manfred Droste

We investigate weighted tree automata over Cauchy tree valuation monoids, a new type of weight structure which includes all commutative semirings and, in addition, average and discounted computations of weights for trees. We define rational tree series over these weight structures, and we prove Kleene's classical theorem for this setting: a tree series over a Cauchy tree valuation monoid is recognizable by a weighted tree automaton if and only if it is rational. The proof works via direct automata-theoretic constructions. Along the way, our results yield a new characterization of weighted tree automata over commutative semirings by rational expressions.

TCS Journal 2015 Journal Article

Characterizing weighted MSO for trees by branching transitive closure logics

• Zoltán Fülöp
• Heiko Vogler

We introduce the branching transitive closure operator on progressing weighted monadic second-order logic formulas where the branching corresponds in a natural way to the branching inherent in trees. For arbitrary commutative semirings, we prove that weighted monadic second order logics on trees is equivalent to the definability by formulas which start with one of the following operators: (i) a branching transitive closure or (ii) one existential second-order quantifier followed by one universal first-order quantifier; in both cases the operator is applied to step-formulas over (a) Boolean first-order logic enriched by modulo counting or (b) Boolean monadic-second order logic.

TCS Journal 2011 Journal Article

Equational tree transformations

• Symeon Bozapalidis
• Zoltán Fülöp
• George Rahonis

We define an equational relation as the union of some components of the least solution of a system of equations of tree transformations in a pair of algebras. We focus on equational tree transformations which are equational relations obtained by considering the least solutions of such systems in pairs of term algebras. We characterize equational tree transformations in terms of tree transformations defined by different bimorphisms. To demonstrate the robustness of equational tree transformations, we give equational definitions of some well-known tree transformation classes for which bimorphism characterizations also exist. These are the class of alphabetic tree transformations, the class of linear and nondeleting extended top-down tree transformations, and the class of bottom-up tree transformations and its linear and linear and nondeleting subclasses. Finally, we prove that a relation is equational if and only if it is the morphic image of an equational tree transformation.

TCS Journal 2011 Journal Article

Varieties of recognizable tree series over fields

• Zoltán Fülöp
• Magnus Steinby

We introduce varieties of recognizable Σ -tree series ( K Σ -VTS for short) over a field K and a ranked alphabet Σ. Our variety theorem establishes a bijective correspondence between these K Σ -VTSs and the varieties of finite-dimensional K Σ -algebras ( K Σ -VFDA for short); a K Σ -algebra is a K -vector space equipped with multilinear Σ -operations. The link between K Σ -VTSs and K Σ -VFDAs is provided by the syntactic K Σ -algebras of tree series. The most immediate predecessors of this study are Berstel’s and Reutenauer’s (1982) [2] work on tree series over fields, Reutenauer’s (1980) [27] theory of varieties of string series, Bozapalidis’ and his associates (1983, 1989, 1991) [8, 5, 4] work on syntactic K Σ -algebras, Steinby’s (1979, 1992) [30, 31] theory of varieties of tree languages, and our previous work (2009) on series of general algebras and their syntactic K Σ -algebras.

TCS Journal 2005 Journal Article

Linear deterministic multi bottom-up tree transducers

• Zoltán Fülöp
• Armin Kühnemann
• Heiko Vogler

In general, top-down and bottom-up tree transducers lead to incomparable classes of tree transformations, both for the nondeterministic and the deterministic case. If deterministic top-down tree transducers are extended by the capability to recognize regular tree properties and deterministic bottom-up tree transducers are generalized by allowing states with arbitrary finite rank, then the two devices, now called deterministic top-down tree transducers with regular look-ahead and deterministic multi bottom-up tree transducers, respectively, become equivalent [Z. Fülöp, A. Kühnemann, H. Vogler, A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead, Inform. Process. Lett. 91 (2004) 57–67]. In this paper we focus on the class ld- MBOT of tree transformations which are computed by linear deterministic multi bottom-up tree transducers. We investigate the relationship among ld- MBOT and the classes of tree transformations computed by (restricted) deterministic bottom-up tree transducers and by (restricted) deterministic top-down tree transducers with regular look-ahead. In fact, we show the inclusion diagram of nine such classes.

TCS Journal 2004 Journal Article

Foreword

• Zoltán Ésik
• Zoltán Fülöp

TCS Journal 2004 Journal Article

Hierarchies of tree series transformations

• Zoltán Fülöp
• Zsolt Gazdag
• Heiko Vogler

We study bottom-up and top-down tree series transducers over a semiring A and denote the tree series transformation classes computed by them by BOT t−ts (A) and TOP t−ts (A), respectively. We present the inclusion diagram of the classes p-BOT t−ts n (A), p-TOP t−ts n (A), p-BOT t−ts n+1(A), and p-TOP t−ts n+1(A) and prove its correctness, where A is a commutative izz-semiring (izz=idempotent, zero-divisor free, and zero-sum free) and the prefix p stands for polynomial. This inclusion diagram implies the properness of the following four hierarchies: p-TOPt−ts(A)⊆p-TOPt−ts 2(A)⊆p-TOPt−ts 3(A)⊆⋯, p-BOTt−ts(A)⊆p-BOTt−ts 2(A)⊆p-BOTt−ts 3(A)⊆⋯, p-TOPt−ts(A)⊆p-BOTt−ts 2(A)⊆p-TOPt−ts 3(A)⊆p-BOTt−ts 4(A)⊆⋯, p-BOTt−ts(A)⊆p-TOPt−ts 2(A)⊆p-BOTt−ts 3(A)⊆p-TOPt−ts 4(A)⊆⋯, where the first hierarchy generalizes the famous top-down tree transformation hierarchy of Engelfriet (Math. Systems Theory 15 (1982) 95–125). As the second main result we prove that the first two hierarchies are proper even for arbitrary (i. e. , not necessarily commutative) izz-semirings.

TCS Journal 2003 Journal Article

Shape preserving top-down tree transducers

• Zoltán Fülöp
• Zsolt Gazdag

As top-down tree transducers generalize generalized sequential machines, shape preserving top-down tree transducers naturally generalize length preserving generalized sequential machines. For instance, top-down relabeling tree transducers are shape preserving top-down tree transducers. We show that a top-down tree transducer is shape preserving if and only if it is equivalent to a top-down relabeling tree transducer. We also prove that it is decidable if a top-down tree transducer is shape preserving.

TCS Journal 1993 Journal Article

Tree transducers with external functions

• Zoltán Fülöp
• Frank Herrmann
• Sándor Vágvölgyi
• Heiko Vogler

In this paper we investigate the computational power of particular tree transducers, viz. , macro tree transducers and attributed tree transducers. The former tree transducers formalize the idea of syntax-directed translation, with the possibility of handling context; the latter tree transducers can serve as a formal model for the reduction semantics of attribute grammars. Here we generalize these tree transducers by allowing the invocation of external functions during the usual rewriting process. The main result of this paper is the characterization of macro tree transducers with external function calls in terms of attributed tree transducers with external function calls. Furthermore, such tree transducers with external function calls induce, in an obvious way, two operators on the set of all classes of tree functions. According to this point of view, we define two classes of tree functions inductively in the same way as the class PREC of primitive recursive tree functions, except that the closure under the scheme of primitive recursion is replaced by the closure under macro tree transducers with external function calls and attributed tree transducers with external function calls, respectively. As a second result of this paper we prove that these two classes are equal to PREC.