Fuzzy tree automata

doi:10.1016/j.fss.2007.02.016

Fuzzy Sets and Systems

Volume 158, Issue 13, 1 July 2007, Pages 1450-1460

https://doi.org/10.1016/j.fss.2007.02.016 Get rights and content

Abstract

In this paper, we map an arbitrary algebra to a completely distributive lattice and define algebras of fuzzy sets. When the algebra is a term algebra, we obtain fuzzy tree languages. After defining fuzzy equational sets, fuzzy rational sets and fuzzy recognizable tree languages, we derive a “Kleene theorem” for fuzzy tree languages.

References (31)

J. Berstel et al.
Recognizable formal power series on trees
Theoret. Comput. Sci.
(1982)
J. Mezei et al.
Algebraic automata and context-free sets
Inform. and Control
(1967)
G. Rahonis
Infinite fuzzy computations
Fuzzy Sets and Systems
(2005)
M.P. Schützenberger
On the definition of a family of automata
Inform. and Control
(1961)
L.A. Zadeh
Fuzzy sets
Inform. and Control
(1965)
H. Bekić, Definable operations in general algebras, and the theory of automata and flowcharts, Technical Report IBM...
J. Berstel, C. Reutenauer, Rational Series and their Languages, EATCS Monographs on Theoretical Computer Science, Vol....
S.L. Bloom et al.
Iteration Theories
(1993)
S.L. Bloom et al.
An extension theorem with an application to formal tree series. Weighted automata: theory and applications (Dresden, 2002)
J. Automat. Lang. Combin.
(2003)
S. Bozapalidis
Effective construction of the syntactic algebra of a recognizable series on trees
Acta Inform.
(1991)

S. Bozapalidis

Equational elements in additive algebras

Theory Comput. Systems

(1999)

J.R. Büchi, On a decision method of restricted second-order arithmetic, in: Proc. 1960 Internat. Congress for Logic,...

P.M. Cohn, Universal Algebra, second ed., Mathematics and its Applications, Vol. 6, D. Reidel Publishing Co.,...

B.A. Davey et al.

Introduction to Lattices and Order

(2002)

J.W. De Bakker, D. Scott, A theory of programs, in: IBM Seminar, Vienna,...

Cited by (40)

Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
2022, Theoretical Computer Science
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.
Lattice-valued tree pushdown automata: Pumping lemma and closure properties
2022, International Journal of Approximate Reasoning
Citation Excerpt :
Fuzzy tree automaton is an extension of tree automaton in the sense of acceptance of trees with a fuzzy membership degree and provides tools for dealing with vaguely defined trees. Ésik and Liu [6] examined fuzzy tree languages over distributive lattices and obtained a Kleene theorem for them. Moreover, a pumping lemma for fuzzy tree languages was presented in [1].
In this paper, we introduce the concept of lattice-valued tree pushdown automata that extends the concepts of lattice-valued pushdown automata, lattice-valued tree automata and fuzzy tree pushdown automata. Also, we consider fuzzy tree languages recognized by lattice-valued (deterministic) tree pushdown automata (called lattice-valued context-free tree languages). Then, we prove the pumping lemma that can be used in proving that certain sets of tree languages are not recognizable. Also, we study closure properties of lattice-valued context-free tree languages with respect to some operations. We show that lattice-valued context-free tree languages recognized by lattice-valued deterministic tree pushdown automata are closed under union, concatenation, star, linear and alphabetic tree homomorphism and inverse tree homomorphism. By applying the pumping lemma on an example, we show that lattice-valued context-free tree languages are not closed under intersection. However, we prove that the intersection of lattice-valued context-free tree language and lattice-valued regular tree language is recognizable by a lattice-valued tree pushdown automaton. Also, we show that lattice-valued non-deterministic tree pushdown automata are only closed under union. However, if $L$ satisfies distributivity, then non-deterministic tree pushdown automata are closed under all of these operations.
Principal abstract families of weighted tree languages
2022, Information and Computation
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).
Syntactic recognizability of graphs with fuzzy attributes
2013, Fuzzy Sets and Systems
We present a syntactic recognition theory for graphs with fuzzy edges and fuzzy nodes by employing the algebraic structure of magmoids. Several examples are illustrated and it is proved that the $α$ -cut of a recognizable set of fuzzy graphs is not always recognizable as a set of crisp graphs. The described theory is then applied for the recognition of fuzzy cognitive maps and the recognizability of interesting examples of sets of fuzzy cognitive maps is examined.
A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices
2024, International Journal of Foundations of Computer Science
Isomorphism between L-valued tree transition systems and upper semilattice
2024, Filomat

View all citing articles on Scopus

^☆: This work was supported in part by the Natural National Science Foundation of China under Grant nos. 60373089 and 30370356 and Agència de Gestió d’Ajuts Universitaris i de Recerca from Spain, and by grant OTKA T46686.

View full text

Fuzzy tree automata☆

Abstract

Theoret. Comput. Sci.

Inform. and Control

Fuzzy Sets and Systems

Inform. and Control

Inform. and Control

Iteration Theories

An extension theorem with an application to formal tree series. Weighted automata: theory and applications (Dresden, 2002)

J. Automat. Lang. Combin.

Effective construction of the syntactic algebra of a recognizable series on trees

Acta Inform.

Equational elements in additive algebras

Theory Comput. Systems

Introduction to Lattices and Order