Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Fundamenta Informati...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
Fundamenta Informaticae
Article . 1997
Data sources: mEDRA
DBLP
Article
Data sources: DBLP
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Natural Computation for Natural Language

Natural computation for natural language
Authors: Carlos Martín-Vide;

Natural Computation for Natural Language

Abstract

Computation not only takes place in provoked contexts of scientific experimentation, but in natural circumstances too. We are going to approach computation in natural contexts. How the nature computes? Turing machines and Chomsky grammars are rewriting systems, and the same is true for Post, Thue, Markov, Lindenmayer and other classes of axiomatic systems. If, among the whole set of natural objects, we focus natural language description, we must say that major trends in contemporary linguistics look at syntax as a rewriting process. Is rewriting unavoidable in this case, does our mind work by rewriting, does the nature compute in this way? We shall attempt to defend that the answer could be negative. The arguments will come from computability theory as well as from linguistics. First we'll formally explain the former ones, then informally the latter ones. With regard to computability theory arguments, we will see that, using the operation of adjoining, a large generative capacity is obtained. This is the case with contextual grammars. It has recently been proved that each recursively enumerable language is the quotient by a regular language of a language generated by a contextual grammar of a particular form. Thus, adjoining (paste) and quotient (cut) lead to computational universality. Recursively enumerable languages can also be characterized as the quotient by a regular language of a language generated by an insertion grammar. The same result is obtained if we take the splicing operation, a formal model of the DNA recombination. This is again a cut-and-paste operation. On the basis of the proof of this result, several further characterizations of recursively enumerable languages have been obtained. Computability theory, then, could be reconstructed without rewriting (and non-terminal symbols) and without any loss in power. Our first aim will be to show some formal aspects of such reconstruction. Later, we'll try to obtain some consequences for the future development of generative theory of natural language.

Related Organizations
Keywords

Natural language processing, mathematical linguistics, computability theory, Formal languages and automata, Models of computation (Turing machines, etc.)

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!