Idempotent tree languages

• Autorzy: Denecke K. , Sarasit N. , Wismath S.
• Języki publikacji: EN

Abstrakty

EN

A tree language of a fixed type τ is any set of terms of type τ. We consider here a binary operation +n on the set Wτ(Xn) of all n-ary terms of type τ, which results in semigroup (Wτ(Xn),+n). We characterize languages which are idempotent with respect to this binary operation, and look at varieties of tree languages containing idempotent languages. We also compare properties of semigroup homomorphisms from (P(Wτ(Xn));+n) to (P(Wτ(Xm));+m) with properties of homomorphisms between the corresponding absolutely free algebras Fτ(Xn) and Fτ(Xm).

Słowa kluczowe

EN

tree language; semigroup; variety of tree languages; idempotence

PL

język drzewa; półgrupa; różnorodność języków drzew

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2013
• Tom: Vol. 46, nr 1
• Strony: 1--14
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Denecke K.

• Institute of Mathematics, University of Potsdam, Potsdam, Germany

autor

Sarasit N.

• Institute of Mathematics, University of Potsdam, Potsdam, Germany

autor

Wismath S.

• Math/C.S. Dept., University of Lethbridge, Lethbridge Ab Canada T1k-3m4

Bibliografia

• [1] K. Denecke, N. Sarasit, Semigroups of tree languages, Asian-European J. Mathematics 1(4) (2008), 489-507.
• [2] K. Denecke, N. Sarasit, Products of tree languages, Bull. Sect. Logic Univ. Łódź 40(1–2) (2011), 13-36.
• [3] F. Gécseg, M. Steinby, Tree Languages, Handbook of Formal Languages, Vol. 3, Springer, Berlin, 1997, 1-68.
• [4] T. Petković, S. Salehi, Positive varieties of tree languages, Theoret. Comput. Sci. 347 (2005), 1-35.
• [5] M. Steinby, Syntactic algebras and varieties of recognizable sets, in: M. Bidoit and M. Dauchet, (eds.) Proc. CAAP’79, (University of Lille, 1979), 226-240.
• [6] M. Steinby, General varieties of tree languages, Theoret. Comput. Sci. 205 (1998), 1-43.
• [7] M. Steinby, A theory of tree language varieties, in: M. Nivat & A. Podelski, Tree Automata and Languages, Elsevier, Amsterdam, (1992).