The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Three models for the description of language
Abstract
We investigate several conceptions of linguistic structure to determine whether or not they can provide simple and "revealing" grammars that generate all of the sentences of English and only these. We find that no finite-state Markov process that produces symbols with transition from state to state can serve as an English grammar. Furthermore, the particular subclass of such processes that producen-order statistical approximations to English do not come closer, with increasingn, to matching the output of an English grammar. We formalize-the notions of "phrase structure" and show that this gives us a method for describing language which is essentially more powerful, though still representable as a rather elementary type of finite-state process. Nevertheless, it is successful only when limited to a small subset of simple sentences. We study the formal properties of a set of grammatical transformations that carry sentences with phrase structure into new sentences with derived phrase structure, showing that transformational grammars are processes of the same elementary type as phrase-structure grammars; that the grammar of English is materially simplified if phrase structure description is limited to a kernel of simple sentences from which all other sentences are constructed by repeated transformations; and that this view of linguistic structure gives a certain insight into the use and understanding of language.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb00917.x · Cited by 48,949
Cited by
The faculty of language: what is it, who has it, and how did it evolve?
Hauser, M. D., Chomsky, N., & Fitch, W. T. (2002) · Science · doi:10.1126/science.298.5598.1569 · Cited by 5,189
Self-citationNatural Language Processing (almost) from Scratch
Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., & Kuksa, P. P. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1103.0398 · Cited by 4,962
The Algorithmic Beauty of Plants
Prusinkiewicz, P., & Lindenmayer, A. (1990) · The Virtual Laboratory · doi:10.1007/978-1-4613-8476-2 · Cited by 2,823
Natural language processing: an introduction
Nadkarni, P. M., Ohno-Machado, L., & Chapman, W. W. (2011) · Journal of the American Medical Informatics Association · doi:10.1136/amiajnl-2011-000464 · Cited by 1,975
A formal theory of inductive inference. Part II
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90131-7 · Cited by 1,758
On certain formal properties of grammars
Chomsky, N. (1959) · Information and Control · doi:10.1016/s0019-9958(59)90362-6 · Cited by 1,588
Self-citationEddy, S. R. (1996) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(96)80056-x · Cited by 1,430
The Mathematics of Sentence Structure
Lambek, J. (1958) · The American Mathematical Monthly · doi:10.1080/00029890.1958.11989160 · Cited by 1,273
A formal theory of inductive inference. Part I
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90223-2 · Cited by 1,192
A probabilistic earley parser as a psycholinguistic model
Hale, J. (2001) · Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001 - NAACL '01 · doi:10.3115/1073336.1073357 · Cited by 1,150
Jumping NLP Curves: A Review of Natural Language Processing Research [Review Article]
Cambria, E., & White, B. (2014) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2014.2307227 · Cited by 1,102
Graves, A., Wayne, G., & Danihelka, I. (2014) · arXiv · doi:10.48550/arxiv.1410.5401 · Cited by 1,058
“Historically, cognitive science and linguistics emerged as fields at roughly the same time as artificial intelligence, all deeply influenced by the advent of the computer (Chomsky, 1956) (Miller, 2003).”
BackgroundInferring statistical complexity
Crutchfield, J. P., & Young, K. (1989) · Physical Review Letters · doi:10.1103/physrevlett.63.105 · Cited by 1,002
Chowdhary, K. R. (2020) · Fundamentals of Artificial Intelligence · doi:10.1007/978-81-322-3972-7_19 · Cited by 1,002
A stochastic parts program and noun phrase parser for unrestricted text
Church, K. W. (1988) · Proceedings of the second conference on Applied natural language processing - · doi:10.3115/974235.974260 · Cited by 957
Organizational Routines as Grammars of Action
Pentland, B. T., & Rueter, H. H. (1994) · Administrative Science Quarterly · doi:10.2307/2393300 · Cited by 936
The Algebraic Theory of Context-Free Languages
(1963) · Studies in Logic and the Foundations of Mathematics · doi:10.1016/s0049-237x(08)72023-8 · Cited by 694
Applications of stochastic context-free grammars using the Inside-Outside algorithm
Lari, K., & Young, S. J. (1991) · Computer Speech & Language · doi:10.1016/0885-2308(91)90009-f · Cited by 639
Topic Modeling in Management Research: Rendering New Theory from Textual Data
Hannigan, T. R., Haans, R. F. J., Vakili, K., Tchalian, H., Glaser, V. L., Wang, M. S., Kaplan, S., & Jennings, P. D. (2019) · Academy of Management Annals · doi:10.5465/annals.2017.0099 · Cited by 621
The reacTable: exploring the synergy between live music performance and tabletop tangible interfaces
Jordà, S., Geiger, G., Alonso, M., & Kaltenbrunner, M. (2007) · Proceedings of the 1st international conference on Tangible and embedded interaction · doi:10.1145/1226969.1226998 · Cited by 619
Self-referencing embedded strings (SELFIES): A 100% robust molecular string representation
Krenn, M., Häse, F., Nigam, A., Friederich, P., & Aspuru‐Guzik, A. (2020) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000128111 · Cited by 618
Representations of Knowledge in Complex Systems
Grenander, U., & Miller, M. I. (1994) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1994.tb02000.x · Cited by 603
Fitch, W. T. (2010) · doi:10.1017/cbo9780511817779 · Cited by 594
MedEx: a medication information extraction system for clinical narratives
Xu, H., Stenner, S. P., Doan, S., Johnson, K. B., Waitman, L. R., & Denny, J. C. (2010) · Journal of the American Medical Informatics Association · doi:10.1197/jamia.m3378 · Cited by 531
Password Cracking Using Probabilistic Context-Free Grammars
Weir, M., Aggarwal, S., Medeiros, B. D., & Glodek, B. (2009) · 2009 30th IEEE Symposium on Security and Privacy · doi:10.1109/sp.2009.8 · Cited by 524
Neurosymbolic AI: the 3rd wave
Garcez, A. D., & Lamb, L. C. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-023-10448-w · Cited by 503
Some psychological studies of grammar.
Miller, G. A. (1962) · American Psychologist · doi:10.1037/h0044708 · Cited by 485
Toward an understanding of flow in video games
Cowley, B., Charles, D., Black, M., & Hickey, R. (2008) · Computers in Entertainment · doi:10.1145/1371216.1371223 · Cited by 479
Dehaene, S., Meyniel, F., Wacongne, C., Wang, L., & Pallier, C. (2015) · Neuron · doi:10.1016/j.neuron.2015.09.019 · Cited by 478
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, C. R., & Crutchfield, J. P. (2001) · Journal of Statistical Physics · doi:10.1023/a:1010388907793 · Cited by 471
Some perceptual consequences of linguistic rules
Miller, G. A., & Isard, S. (1963) · Journal of Verbal Learning and Verbal Behavior · doi:10.1016/s0022-5371(63)80087-0 · Cited by 468
Songs to syntax: the linguistics of birdsong
Berwick, R. C., Okanoya, K., Beckers, G. J. L., & Bolhuis, J. J. (2011) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2011.01.002 · Cited by 467
Using Statistics in Lexical Analysis
Church, K., Gale, W., Hanks, P., & Hindle, D. (2021) · Lexical Acquisition: Exploiting On-Line Resources to Build a Lexicon · doi:10.4324/9781315785387-8 · Cited by 459
Zhang, J., & El-Gohary, N. M. (2016) · Journal of Computing in Civil Engineering · doi:10.1061/(asce)cp.1943-5487.0000346 · Cited by 414
Pirahã exceptionality: A reassessment
Nevins, A., Pesetsky, D., & Rodrigues, C. (2009) · Language · doi:10.1353/lan.0.0107 · Cited by 404
Natural language based financial forecasting: a survey
Xing, F. Z., Cambria, E., & Welsch, R. E. (2018) · Artificial Intelligence Review · doi:10.1007/s10462-017-9588-9 · Cited by 398
(1968) · doi:10.1007/978-1-4615-9050-7_2 · Cited by 395
Some Effects of Semantic and Grammatical Context on the Production and Perception of Speech
Lieberman, P. (1963) · Language and Speech · doi:10.1177/002383096300600306 · Cited by 394
Chomsky, N., & Miller, G. A. (1958) · Information and Control · doi:10.1016/s0019-9958(58)90082-2 · Cited by 383
Self-citationFrequency of basic English grammatical structures: A corpus analysis
Roland, D., Dick, F., & Elman, J. L. (2007) · Journal of Memory and Language · doi:10.1016/j.jml.2007.03.002 · Cited by 379
The estimation of stochastic context-free grammars using the Inside-Outside algorithm
Lari, K., & Young, S. J. (1990) · Computer Speech & Language · doi:10.1016/0885-2308(90)90022-x · Cited by 379
On the Evolutionary Origin of Prospect Theory Preferences
McDermott, R., Fowler, J. H., & Smirnov, O. (2008) · The Journal of Politics · doi:10.1017/s0022381608080341 · Cited by 370
Prolog and Natural Language Analysis
Harrison, S. P., Pereira, F. C. N., & Shieber, S. M. (1988) · Language · doi:10.2307/414538 · Cited by 364
Segregating the core computational faculty of human language from working memory
Makuuchi, M., Bahlmann, J., Anwander, A., & Friederici, A. D. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0810928106 · Cited by 364
Clinical Problem Solving: A Behavioral Analysis
KASSIRER, J. P., & GORRY, G. A. (1978) · Annals of Internal Medicine · doi:10.7326/0003-4819-89-2-245 · Cited by 352
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Verdu, S. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720531 · Cited by 316
Uncertainty About the Rest of the Sentence
Hale, J. (2006) · Cognitive Science · doi:10.1207/s15516709cog0000_64 · Cited by 296
Towards a generative syntax of tonal harmony
Rohrmeier, M. (2011) · Journal of Mathematics and Music · doi:10.1080/17459737.2011.573676 · Cited by 295
The induction of dynamical recognizers
Pollack, J. B. (1991) · Machine Learning · doi:10.1007/bf00114845 · Cited by 294
Holloway (1969) · Current Anthropology · doi:10.1086/201036 · Cited by 288
The learnability of abstract syntactic principles
Perfors, A., Tenenbaum, J. B., & Regier, T. (2011) · Cognition · doi:10.1016/j.cognition.2010.11.001 · Cited by 285
The Information Conveyed by Words in Sentences
Hale, J. (2003) · Journal of Psycholinguistic Research · doi:10.1023/a:1022492123056 · Cited by 283
The use of positional information in the modeling of plants
Prusinkiewicz, P., Mündermann, L., Karwowski, R., & Lane, B. (2001) · Proceedings of the 28th annual conference on Computer graphics and interactive techniques · doi:10.1145/383259.383291 · Cited by 276
Li, H.-L., Pang, Y.-H., & Liu, B. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkab829 · Cited by 269
Learning Long-Distance Phonotactics
Heinz, J. (2010) · Linguistic Inquiry · doi:10.1162/ling_a_00015 · Cited by 257
Yang, Q., Zhang, Y., Dai, W., & Pan, S. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781139061773 · Cited by 254
Grammatical Models of Organizational Processes
Pentland, B. T. (1995) · Organization Science · doi:10.1287/orsc.6.5.541 · Cited by 233
Compositionality Decomposed: How do Neural Networks Generalise?
Hupkes, D., Dankers, V., Mul, M., & Bruni, E. (2020) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.11674 · Cited by 194
Opportunities and challenges of text mining in materials research
Kononova, O., He, T., Huo, H., Trewartha, A., Olivetti, E. A., & Ceder, G. (2021) · iScience · doi:10.1016/j.isci.2021.102155 · Cited by 182
Albahra, S., Gorbett, T., Robertson, S., D'Aleo, G., Kumar, S. V. S., Ockunzzi, S., Lallo, D., Hu, B., & Rashidi, H. H. (2023) · Seminars in Diagnostic Pathology · doi:10.1053/j.semdp.2023.02.002 · Cited by 139
Large Language Models versus Natural Language Understanding and Generation
Karanikolas, N., Manga, E., Samaridi, N., Tousidou, E., & Vassilakopoulos, M. (2023) · Proceedings of the 27th Pan-Hellenic Conference on Progress in Computing and Informatics · doi:10.1145/3635059.3635104 · Cited by 102
The emergence of hierarchical structure in human language
Miyagawa, S., Berwick, R. C., & Okanoya, K. (2013) · Frontiers in Psychology · doi:10.3389/fpsyg.2013.00071 · Cited by 81
“Contemporary human language syntax cannot be characterized by any finite state grammar (Chomsky, 1956).”
BackgroundA bird's eye view of human language evolution
Berwick, R. C., Beckers, G. J. L., Okanoya, K., & Bolhuis, J. J. (2012) · Frontiers in Evolutionary Neuroscience · doi:10.3389/fnevo.2012.00005 · Cited by 81
“Long-standing results (Chomsky,1956; Rabin and Scott, 1959) demonstrate that such patterns cannot be generated by any finite-state transition network, because, for example, in order ensure that each warble i on the left is matched with its corresponding rattle i on the right one must in effect be…”
Cognitive Architectures for Language Agents
Sumers, T. R., Yao, S., Narasimhan, K., & Griffiths, T. L. (2023) · arXiv · doi:10.48550/arxiv.2309.02427 · Cited by 798
“String rewriting plays a significant role in the theory of formal languages, corresponding to Chomsky’s phrase structure grammar (Chomsky, 1956).”
BackgroundOne model for the learning of language
Yang, Y., & Piantadosi, S. T. (2022) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2021865119 · Cited by 50
“sis is also shown. 3 Learning simple formal languages We rst study the model’s ability to learn several simple formal languages that are motivated by the structures present in natural language. Since Chomsky (1956), numerous authors have attempted to pinpoint what type of computational system supports natural language…”
Language models: past, present, and future
Li, H. (2022) · Communications of the ACM · doi:10.1145/3490443 · Cited by 45
The Cambridge Handbook of Working Memory and Language
(2022) · doi:10.1017/9781108955638 · Cited by 43
Technological complexity and the global dispersal of modern humans
Hoffecker, J. F., & Hoffecker, I. T. (2017) · Evolutionary Anthropology: Issues, News, and Reviews · doi:10.1002/evan.21553 · Cited by 31
Bialek, W. (2007) · Les Houches - Ecole d’Ete de Physique Theorique · doi:10.1007/3-540-45701-1_12 · Cited by 16
Hupkes, D., Veldhoen, S., & Zuidema, W. (2018) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.11196 · Cited by 14
On the Linguistic Capacity of Real-Time Counter Automata
Merrill, W. (2020) · arXiv · doi:10.48550/arxiv.2004.06866 · Cited by 12
Extracting reaction networks from databases—opening Pandora’s box
Fearnley, L. G., Davis, M. J., Ragan, M. A., & Nielsen, L. K. (2014) · Briefings in Bioinformatics · doi:10.1093/bib/bbt058 · Cited by 9
Learning Program Behavioral Models from Synthesized Input–Output Pairs
Mammadov, T., Klakow, D., Koller, A., & Zeller, A. (2026) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3748720 · Cited by 5
Randomized Positional Encodings Boost Length Generalization of Transformers
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J. (2023) · arXiv · doi:10.48550/arxiv.2305.16843 · Cited by 1
Learning Program Behavioral Models from Synthesized Input-Output Pairs
Mammadov, T., Klakow, D., Koller, A., & Zeller, A. (2024) · arXiv · doi:10.48550/arxiv.2407.08597
Metadata
- Authors
- Chomsky, N.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1956-09
- Volume
- 2
- Issue
- 3
- Pages
- 113-124
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2124479173
- Cited by
- 2,796
- References
- 1
- FWCI
- 135.61
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.