iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/3-540-45446-2_11
Some Structural Properties of Associative Language Descriptions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Some Structural Properties of Associative Language Descriptions

  • Conference paper
  • First Online:
Theoretical Computer Science (ICTCS 2001)

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

Included in the following conference series:

  • 412 Accesses

Abstract

The Associative Language Description model (ALD), a combination of locally testable and constituent structure ideas, has been recently proposed to overcome some criticisms relative to context-free languages. This approach is consistent with current views on brain organization and can conveniently describe typical technical languages such as Pascal or HTML. ALD languages are strictly enclosed in context-free languages but in practice the ALD model equals context-free grammars in explanatory adequacy. Moreover, it excludes mathematical sets based on counting properties that are never used in the definition of artificial languages. Many properties of ALD are still to be investigated. Here, a characterization of context free languages in term of ALD languages is proved and a new hierarchy in the ALD family is given.

Work partially supported by CNR-CESTIA.

Lecturer of Formal Languages, Università Svizzera Italiana

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Crespi Reghizzi, G. Guida, D. Mandrioli, Non-counting context-free languages, Journ. ACM, 25 (1978), 4, 571–580.

    Article  MATH  MathSciNet  Google Scholar 

  2. W. Thomas, On Noncounting Tree Languages, Grundl. Theor. Informatik, Proc. First Int. Workshop, Paderborn 1982, 234–242.

    Google Scholar 

  3. A. Cherubini, S. Crespi, P. San Pietro, Languages Based on Structural Local Testability, in C.S. Calide, M.J. Dinneen, Proceedings of DMTCS’99, Auckland, New Zealand, 18–21, January 1999, Springer, Singapore.

    Google Scholar 

  4. V. Braitenberg and F. Pulvermüller, Entwurf einer neurologischen Theorie der Sprache, Naturwissenschaften 79 (1992), 103–117.

    Article  Google Scholar 

  5. A. Cherubini, S. Crespi Reghizzi, P. San Pietro, Associative Language Descriptions, Theoretical Computer Science, 2001 (to appear)

    Google Scholar 

  6. S. Crespi Reghizzi, M. Pradella, P. San Pietro, Associative definitions of programming languages, Computer Languages, 26(2:4), 2001.

    Google Scholar 

  7. M. Harrison, Introduction to Formal Language Theory, Addison Wesley (1978).

    Google Scholar 

  8. S. Marcus, Contextual Grammars and Natural Languages, Handbook of formal languages (Eds. G. Rozenberg, A. Saloma), Vol.II, Ch.6, Springer (1997), 215–132.

    Google Scholar 

  9. A. Ehrenfeucht, G. Päun and G. Rozenberg, Contextual Grammars and Formal Languages, Handbook of formal languages (Eds. G. Rozenberg, A. Saloma), Vol.II, Ch.6, Springer (1997), 237–290.

    Google Scholar 

  10. S. Crespi-Reghizzi and V. Braitenberg, Towards a brain compatible theory of syntax based on local testability, in C. Martin-Vide and V. Mitrana (eds) Grammars and Automata for String Processing: from Mathematics and Computer Science to Biology, and Back. Gordon and Breach, London, 2001.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Politecnico di Milano, P.za L. da Vinci 32, 20133, Milano, Italia

    Alessandra Cherubini

  2. Dipartimento di Elettronica e Informazione, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133, Milano, Italia

    Stefano Crespi Reghizzi & Pierluigi San Pietro

Authors
  1. Alessandra Cherubini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefano Crespi Reghizzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pierluigi San Pietro
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cherubini, A., Crespi Reghizzi, S., San Pietro, P. (2001). Some Structural Properties of Associative Language Descriptions. In: Theoretical Computer Science. ICTCS 2001. Lecture Notes in Computer Science, vol 2202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45446-2_11

Download citation

  • DOI: https://doi.org/10.1007/3-540-45446-2_11

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42672-1

  • Online ISBN: 978-3-540-45446-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation