×

Codes and equations on trees. (English) Zbl 0974.68095

Summary: The objective of this paper is to study, by new formal methods, the notion of tree code introduced by M. Nivat in [Nivat, Maurice (ed.) et al., Tree automata and languages. Amsterdam etc.: North-Holland. Stud. Comput. Sci. Artif.Intell. 10, 1-19 (1992; Zbl 0798.68083)]. In particular, we consider the notion of stability for sets of trees closed under concatenation. This allows us to give a characterization of tree codes which is very close to the algebraic characterization of word codes in terms of free monoids. We further define the stable hull of a set of trees and derive a defect theorem for trees, which generalizes the analogous result for words. As a consequence, we obtain some properties of tree codes having two elements. Moreover, we propose a new algorithm to test whether a finite set of trees is a tree code. The running time of the algorithm is polynomial in the size of the input. We also introduce the notion of tree equation as complementary view to tree codes. The main problem emerging in this approach is to decide the satisfiability of tree equations: it is a special case of second-order unification, and it remains still open.

MSC:

68Q45 Formal languages and automata
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Keywords:

tree code

Citations:

Zbl 0798.68083
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York · Zbl 1022.94506
[2] Berstel, J.; Perrin, D.; Perrot, J.F.; Restivo, A., Sur le theoreme des defaut, J. algebra, 60, 169-180, (1979) · Zbl 0421.20027
[3] C. Choffrut, J. Karhumäki, Combinatorics on words, in: G. Rozenberg, A. Salomaa, Handbook of Formal Languages, Vol. 3, Springer, Berlin, 1997.
[4] Chrobak, M.; Rytter, W., Unique decipherability for partially commutative alphabets, Fund. inform., X, 323-336, (1987) · Zbl 0634.94014
[5] Eilenberg, S., Automata, languages and machines, vol. A, (1974), Academic Press New York · Zbl 0317.94045
[6] Elgot, C.C.; Bloom, S.L.; Tindell, R., On the algebraic structure of rooted trees, J. comput. system sci., 16, 362-399, (1978) · Zbl 0389.68007
[7] F. Gécseg, M. Steinby, Tree languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 3, Springer, Berlin, 1997.
[8] D. Giammarresi, S. Mantaci, F. Mignosi, A. Restivo, Congruence, Automata and Periodicities, in: J. Almeida, G.M.S. Gomes, P.V. Silva (Eds.), Proc. Semigroups, Automata and Languages, Portugal, 1994, (World Scientific Publishing, Singapore, 1996, pp. 125-135.
[9] D. Giammarresi, S. Mantaci, F. Mignosi, A. Restivo, A periodicity theorem for trees, Proc. 13th. World Computer Congress - IFIP’94, Vol. A-51, Elsevier Science B.V., North-Holland, Amsterdam, 1994, pp. 473-478.
[10] Giammarresi, D.; Mantaci, S.; Mignosi, F.; Restivo, A., Periodicities on trees, Theoret. comput. sci., 205, 1-2, 145-181, (1998) · Zbl 0913.68150
[11] Goldfarb, W., The undecidability of the second-order unification problem, Theoret. comput. sci., 13, 225-230, (1981) · Zbl 0457.03006
[12] Hoogeboom, H.J.; Muscholl, A., The code problem for traces – improving the boundaries, Theoret. comput. sci., 172, 309-321, (1997) · Zbl 0903.68129
[13] Jaffar, J., Minimal and complete word unification, J. ACM, 37, 47-85, (1990) · Zbl 0697.68052
[14] Karhumäki, J.; Mantaci, S., Defect theorems for trees, Fund. inform., 38, 119-133, (1999) · Zbl 0935.68083
[15] J. Karhumäki, S. Mantaci, Defect theorems for trees, (Conference Version), Proc. of Developments in Language Theory (1999), to appear.
[16] A. Lentin, M.P. Schützenberger, A combinatorial problem in the theory of free monoids, Proc. University of North Carolina, 1967, pp. 67-85.
[17] Lothaire, M., Combinatorics on words, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045
[18] Lyndon, R.C.; Schützenberger, M.P., The equation \(a\^{}\{m\} = b\^{}\{n\}c\^{}\{p\}\) in a free group, Michigan math. J., 9, 289-298, (1962) · Zbl 0106.02204
[19] Makanin, G.S., The problem of solvability of equations in a free semigroup, Math. USSR sbornik, 32, 129-198, (1977), in AMS, 1979 · Zbl 0396.20037
[20] S. Mantaci, D. Micciancio, An algorithm for the solution of tree equations, Proc. CAAP-TAPSOFT’97, Lecture Notes in Computer Science, Vol. 1214, 1997, pp. 417-428.
[21] S. Mantaci, A. Restivo, Equations on trees, Proc. MFCS’96, Lecture Notes in Computer Science, Vol. 1113, 1996, pp. 443-456. · Zbl 0886.05050
[22] S. Mantaci, A. Restivo, Tree codes and equations, Proc. 3rd Internat. Conf. Developments in Language Theory, 1997, pp. 119-133.
[23] S. Mantaci, A. Restivo, On the defect theorem for trees, Proc. “8th Internat. Conf. Automata and Formal Languages”, Salgótarján, Ungheria, Pub. Math, Debrecen 54-supplement (1999) 923-932. · Zbl 0981.05026
[24] Matyiasevitch, Y., Mots et codes. cas décidables et indécidables di problème du codage pour LES monoı̈des partialment commutatifs, Quadrature. mag. math. pure app., 27, 23-33, (1997)
[25] Nivat, M., (), 1-19
[26] L. Oget, A least common divisor for trees, Internal Report.
[27] J. Tatcher, Tree automata, an informal survey, in: A. Aho (Ed.), Currents in the Theory of Computing, Pretince-Hall, Englewood Cliffs, NJ, 1973.
[28] W. Thomas, Logical aspects in the theory of tree languages, in: B. Courcelle (Ed.), Proc. 9 colloquium on Trees in Algebra and Programming, Cambridge University Press, Cambridge, 1984. · Zbl 0557.68051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.