Computing Languages by (Bounded) Local Sets

  • Dora Giammarresi
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


We introduce the definition of local structures as description of computations to recognize strings and characterize families of Chomsky’s hierarchy in terms of projection of frontiers of local sets of structures. Then we consider particular grid structures we call bounded-grids and study the corresponding family of string languages by proving some closure properties and giving several examples.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    R.V. Book. Time-bounded grammars and their languages. Journal of Computer System Science. Vol 5, pp. 397–429, 1971.zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    G. Buntrok and F. Otto Growing Context-Sensitive Languages and Church-Rosser Languages. Information and Computation. Vol 141, pp. 1–36, 1998.CrossRefMathSciNetGoogle Scholar
  3. 3.
    S. Eilenberg. Automata, Languages and Machines. Vol. A, Academic Press, 1974.Google Scholar
  4. 4.
    M.J. Fischer Two characterizations of the context-sensitive languages. Prc. 10th Annual IEEE Symp. on Switching and Automata Theory, pp. 157–165, 1969.Google Scholar
  5. 5.
    D. Giammarresi and A. Restivo. Two-dimensional finite state recognizability. Fundamenta Informaticae. vol. 25, no. 3,4, pp. 399–422, 1996.zbMATHMathSciNetGoogle Scholar
  6. 6.
    D. Giammarresi, A. Restivo. “Two-dimensional languages”. In Handbook of Formal Languages, G. Rosenberg et al., Eds, Vol. III, pp. 215–268. Springer Verlag, 1997.Google Scholar
  7. 7.
    A.W. Gladkij. “On the complexity of derivations in context-sesitive grammars”. In Algebri i Logika Sem., vol. 3, pp. 29–44, 1964.zbMATHGoogle Scholar
  8. 8.
    J.E. Hopcroft, and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979.zbMATHGoogle Scholar
  9. 9.
    M. Latteux and D. Simplot. Context-sensitive string languages and recognizable picture languages. Information and Computation, Vol. 138,2, pp. 160–169, 1997.zbMATHCrossRefMathSciNetGoogle Scholar
  10. 10.
    M. Latteux, D. Simplot and A. Terlutte. Iterated length-preserving rational trasductions. Proc. MFCS’98, LNCS Vol. 1450, pp. 286–295. Springer-Verlag, 1998.Google Scholar
  11. 11.
    R. McNaughton. An insertion into the Chomsky Hierarchy? Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, J. Karhumaki et al., Eds), pp. 204–212. Springer-Verlag, 1999.Google Scholar
  12. 12.
    J. Mezei and J.B. Wright. Algebraic automata and context-free sets. Information and Computation, Vol. 11, pp. 3–29, 1967.zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Dora Giammarresi
    • 1
  1. 1.Dipartimento di MatematicaUniversità di Roma “Tor Vergata”RomaItaly

Personalised recommendations