On reverse and general definite tree languages | SpringerLink
Skip to main content
Springer Nature Link
Log in

On reverse and general definite tree languages

Extended abstract

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1992)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 623))

Included in the following conference series:

  • 156 Accesses

Abstract

We show: There is no tree language whose syntactic semigroup lies in Kr, or in LI unless it is in K. Instead, reverse (resp. general) definite tree languages have syntactic semigroups in Kr V J1 (resp. LI v J1). We give concise combinatorial descriptions of the tree languages whose syntactic semigroups are in Kr v J 1 (resp. LI v J 1), in terms of the properties reverse (resp. general) J 1-definite. These properties are more general than the properties reverse (general) definite as defined by Heuter. Finally we show that they are decidable.

Supported by an NSERC postdoctoral fellowship.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Eilenberg, Automata, Languages and Machines, Vol. B, Academic Press, 1976.

    Google Scholar 

  2. F. Gécsec, M. Steinby. Tree Automata. (Akademiai Kiado, Budapest, 1984).

    Google Scholar 

  3. U. Heuter, Definite tree languages, Bulletin of the EATCS 35, 1988, 137–142.

    Google Scholar 

  4. U. Heuter, Generalized definite tree languages, Proc. 14th MFCS, Lecture Notes in Computer Science 379, Springer, 1989, 270–280.

    Google Scholar 

  5. U. Heuter, Zur Klassifizierung reguläler Baumsprachen. Dissertation, University of Aachen (1989), Aachen, FRG.

    Google Scholar 

  6. M. Nivat and A. Podelski, Tree monoids and recognizable sets of trees, in H. Aït-Kaci and M. Nivat eds., Resolution of Equations in Algebraic Structures, Vol. 1, Academic Press, 1989.

    Google Scholar 

  7. N. Nivat and A. Podelski, Definite tree languages (cont'd), Bulletin of the EATCS 38, 1989, 186–190.

    Google Scholar 

  8. A. Podelski, Monoïdes d'Arbres et Automates d'Arbres, Thèse de Doctorat, Université Paris 7, 1989.

    Google Scholar 

  9. J. E. Pin, Variétés de langages formels, Masson, Paris, 1984, and Varieties of Formal Langages, Plenum, London, 1986.

    Google Scholar 

  10. M. Steinby, Syntactic algebras and varieties of recognizable sets, in Les arbres en algèbre et en programmation, 4ième Coll. Lille (Proc. Coll., Lille 1979) Université de Lille, 226–240.

    Google Scholar 

  11. M. Steinby, “A Theory of Tree Language Varieties,” in: Nivat, M., and Podelski, A., eds., Trees, Automata and Languages, Elsevier Publishers, 1991.

    Google Scholar 

  12. J.W. Thatcher, J.B. Wright, “Generalized Finite Automata Theory with an Application to a Decision Problem of Second Order Logic”, Math.Syst. Th. 2 (1968).

    Google Scholar 

  13. W. Thomas, On noncounting tree languages, Grundl. Theor. Informatik (Proc. 1. Intern. Workshop, Paderborn 1982), 234–242.

    Google Scholar 

  14. W. Thomas, Logical aspects in the study of tree languages, Proc. Ninth Coll. on Trees in Algebra and in Programming, Cambrige Univ. Press, 1984, 31–49.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Comp. Sci., McGill University, 3480 University Street, H3A 2A7, Montréal, Québec, Canada

    Pierre Péladeau

  2. L.I.T.P., Université Paris 7, 2 place Jussieu, 75005, Paris, France

    Andreas Podelski

Authors
  1. Pierre Péladeau
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andreas Podelski
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

W. Kuich

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Péladeau, P., Podelski, A. (1992). On reverse and general definite tree languages. In: Kuich, W. (eds) Automata, Languages and Programming. ICALP 1992. Lecture Notes in Computer Science, vol 623. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55719-9_71

Download citation

  • DOI: https://doi.org/10.1007/3-540-55719-9_71

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-55719-7

  • Online ISBN: 978-3-540-47278-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation