Skip to main content
SpringerLink
Log in

Languages accepted by systolic Y-tree automata: structural characterizations

  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract

In this paper closure properties and decision problems for families of languages accepted by deterministic and nondeterministic systolic binary Y-tree automata are studied. Non closure results under basic language operations are stated by means of new nonacceptability criteria for these classes of automata. Necessary and sufficient conditions are given in terms of the shape of the underlying Y-tree, for the closure under λ-free regular substitution, concatenation, inverse homomorfism and for the closure under right concatenation with and quotient by finite sets. Moreover in the nondeterministic case necessary and sufficient conditions are given again in terms of the shape of the underlying Y-tree for the closure under right concatenation with regular sets and for the decidability of the problems of emptiness, finiteness, equivalence and co-emptiness. A sufficient condition is given for the decidability of the stability problem, in the deterministic case, while some undecidability results are proved in the nondeterministic case.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Culik, K. II, Gruska, J., Salomaa, A.: Systolic automata for VLSI on balanced tree. Acta Inf.18, 335–344 (1983)

    Google Scholar 

  2. Culik, K. II, Gruska, J., Salomaa, A.: On a family of L languages resulting from systolic tree automata. Theoret. Comput. Sci.23, 231–242 (1983)

    Google Scholar 

  3. Culik, K. II, Gruska, J., Salomaa, A.: Systolic trellis automata. Int. J. Comput. Math.15, 195–212 (1984);16, 3–22 (1984)

    Google Scholar 

  4. Culik, K. II., Gruska, J., Salomaa, A.: Systolic trellis automata: Stability, decidability and complexity. Inf. Control 71,2, 18–230 (1986)

    Google Scholar 

  5. Culik, K. II, Salomaa, A., Wood, D.: Systolic tree acceptors. R.A.I.R.O. Inf. Théor.18, 53–69 (1984)

    Google Scholar 

  6. Fachini, E., Francese R., Napoli, M., Parente, D.: BC-tree systolic automata: Characterization and properties. J. Comput. Artif. Intell.8, 53–82 (1989)

    Google Scholar 

  7. Fachini, E., Gruska, J., Napoli, M., Parente, D.: Power of interconnection and of nondeterminism in regular Y-tree systolic automata (in preparation)

  8. Fachini, E., Iania, L.: A note on the paper “Systolic tree acceptors” by K. Culik, A. II, Saloma and Wood, D. Bull. EATCS28, 26–30 (1986)

    Google Scholar 

  9. Fachini, E., Napoli, M.: C-tree systolic automata. Theor. Comput. Sci.56, 155–186 (1988)

    Google Scholar 

  10. Fachini, E., Maggiolo Schettini, A., Resta, G., Sangiorgi, D.: Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata. Theor. Comput. Sci.83(2), 249–260 (1991)

    Google Scholar 

  11. Fachini, E., Maggiolo Schettini, A., Resta, G., Sangiorgi, D.: Some structural properties of systolic tree automata. Fundam. Inf.12(4), 571–586 (1989)

    Google Scholar 

  12. Fachini, E., Maggiolo Schettini, A., Sangiorgi, D.: Comparisons among classes of Y-tree systolic automata. Proc. Fifteenth Intern. Symp. MFCS (Lect. Notes Comput. Sci., vol. 452, pp 254–260). Berlin Heidelberg New York: Springer 1990

    Google Scholar 

  13. Fachini, E., Maggiolo Schettini, A., Sangiorgi, D.: Comparisons among classes of Y-tree systolic automata and systolic trellis automata (in preparation)

  14. Gruska, J.: Systolic automata: Power, characterizations, nonhomogenity. Proc. Nineth Intern. Symp. MFCS (Lect. Notes Comput. Sci., vol. 176, pp. 32–49). Berlin Heidelberg New York: Springer 1984

    Google Scholar 

  15. Gruska, J.: Synthesis, structure and power of systolic computations. Theor. Comput. Sci.71, 47–78 (1990)

    Google Scholar 

  16. Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979

    Google Scholar 

  17. Ibarra, O.H., Kim, S.M.: A characterization of systolic binary tree automata and applications. Acta Inf.21, 193–207 (1984)

    Google Scholar 

  18. Monti, A., Parente, D.: Systolic tree with base automata. Int. J. Found. Comput. Sci.2, 221–235 (1991)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Ingegneria Elettronica, II Università di Roma “Tor Vergata”, Viale della ricerca scientifica, I-00173, Roma, Italy

    E. Fachini

  2. Dipartimento di Informatica ed Applicazioni, Università di Salerno, I-84081, Baronissi, Italy

    A. Monti, M. Napoli & D. Parente

Authors
  1. E. Fachini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Monti
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Napoli
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. D. Parente
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Work partially supported by the Italian Ministry of the University and of Scientific Research in the framework of the project “Modelli e specifiche per sistemi concorrenti”.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fachini, E., Monti, A., Napoli, M. et al. Languages accepted by systolic Y-tree automata: structural characterizations. Acta Informatica 29, 761–778 (1992). https://doi.org/10.1007/BF01191895

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01191895

Keywords

Search

Navigation