article

Free access

A finite and real-time processor for natural language

Author:

Glenn D. BlankAuthors Info & Claims

Communications of the ACM, Volume 32, Issue 10

Pages 1174 - 1189

https://doi.org/10.1145/67933.67935

Published: 01 October 1989 Publication History

PDF eReader

Abstract

People process natural language in real time and with very limited short-term memories. This article describes a computational architecture for syntactic performance that also requires fixed finite resources.

References

[1]

Barton, G., Berwick, R., and Ristad, E. Computational Complexity and Natural Language. MIT Press, Cambridge, Mass., 1987.

Digital Library

Google Scholar

[2]

Bever, T., Garrett, M., and Hartig. R. The interaction of perceptual processes and ambiguous sentences. Memory and Cognition 1, 3 (1973), 277-286.

Crossref

Google Scholar

[3]

Blank, G. Responsive system control using register vector grammar. In Proceedings of the IEEE International Symposium on Intelligent Control (Philadelphia, Penn., Jan. 19-20, 1987), pp. 461-466.

Google Scholar

[4]

Blank, G. Register vector grammar: A new kind of finite state automaton. In Proceedings of the Ninth International C~nference on Artificial Intelligence (UCLA, Aug. 18-23, 1985), pp. 749--756.

Google Scholar

[5]

Bresnan, J., Kaplan, R., Peters, S., and Zaenan, A. Cross-serial dependencies in Dutch. Linguistic Inquiry I3, 4 (1982!, 613-635.

Google Scholar

[6]

Carrithers, C., and Bever, T. Eye-fixation patterns during reading confirm theories of language comprehension. Cog. Sci. 8, 2 (1984), 157-172.

Google Scholar

[7]

Chomsky, N. Syntactic structures. Mouton, The Hague, Netherlands, 1957.

Google Scholar

[8]

Church, K. On memory limitations in natural language processing. IU Linguistics Club, Bloomington, Ind., 1982.

Google Scholar

[9]

Cowper, E. Constraints on sentence complexity: A model for syntactic processing. Ph.D. dissertation, Brown University, 1976.

Google Scholar

[10]

Earley, J. An efficient context-free algorithm. Commun. ACM 6, 8 (Aug. 1970}, 94-102,

Digital Library

Google Scholar

[11]

Frazier, L., and Fodor, J. The sausage machine: A new two-stage parsing model. Cognition 6, 4 (19781, 291-295.

Crossref

Google Scholar

[12]

Garrett, M., and Bever, T, The perceptual segmen'Iation of sentences. In The Structure and Psychology of Language, T. Bever and W. Weksel, Eds. Holt, Rinehart & Winston, New York, 1970.

Google Scholar

[13]

Gazdar, G., Klein, E., Pullum, G., and Sag, I. Generalized Phrase Structure Grammar. Harvard University Press, Cambridge, Mass., 1985.

Google Scholar

[14]

Hale, K. On the position of Walpiri in a typology of the base. Indiana University Linguistics Club, Bloomington, Ind., 1981.

Google Scholar

[15]

Kimball, J. Seven principles of surface structure parsing in natural language. Cognition 2, 1 (1973), 15-47.

Crossref

Google Scholar

[16]

Kunst, A. Petri net automata and the representation of natural languages. Unpublished MS.

Google Scholar

[17]

Kunst, A., and Blank, G. Processing morphology: Words and cliches. In Computing in the Humanities, R.W. Bailey, Ed. North-Holland, The Hague (1982}, 123-131.

Google Scholar

[18]

Langendoen, D. Finite-state parsing of phrase-structure languages and the status of readjustment rules in grammar. Linguistic Inquiry 6, 4 {1975), 533-554.

Google Scholar

[19]

Langendoen, D., and Langsam, Y. The representation of constituent structures for finite-state parsing. In Proceedings of 22nd Annual Meeting of the Association for Computational Linguistics. (Stanford, Calif., 1984), pp. 24-27.

Digital Library

Google Scholar

[20]

Marcus, M. A theory of syntactic recognition for natural language. MIT Press, Cambridge, Mass., 1980.{

Digital Library

Google Scholar

[21]

Martin, W., Church, K., and Patti, R. Preliminary analysis of a breadth-first parsing algorithm: Theoretical and experimental results, in Natural Language Parsing Systems. L. Bolc, Ed. Springer Verlag, Berlin, 1987.

Digital Library

Google Scholar

[22]

Miller, G., and Chomsky, N. Finitary models of language users. In Handbook of Mathematical Psychology, R. D. Luce et al., Eds. Wiley, New York, 1963.

Google Scholar

[23]

Milne, R. Resolving lexical ambiguity in a deterministic parser. Comp. Ling. 12, 1 l1986), 1-12.

Digital Library

Google Scholar

[24]

Pullum, G, Syntactic and semantic parsability. In Proceedings of COLING84 (Stanford University, July 1984), pp. 112-122.

Digital Library

Google Scholar

[25]

Reed, J. An efficient context-free parsing algorithm based on Register Vector Grammars. In Proceedings of the Third Annual IEEE Conference on Expert Systems in Government. (i987), pp. 34-40.

Google Scholar

[26]

Reed, I. Compiling phrase structure rules into Register Vector Grammar. In Proceedings of the Fifth Annual IEEE Conference on AI Systems in Government. 0989).

Google Scholar

[27]

Reich, P. The finiteness of natural language. Language 45, 4 (1969}, 831-43.

Crossref

Google Scholar

[28]

Ross, J. Constraints on Variables in Syntax. Ph.D. dissertation, M{T, Cambridge, Mass., 1967.

Google Scholar

[29]

Schegloff, E. The relevance of repair to syntax-for-conversation. In Syntax and Semantics, 12: Discourse and Syntax, Academic Press, New York, 1979, pp. 261-288.

Google Scholar

[30]

Shieber, S. Direct parsing of ID/LP grammars. Ling. Phil. 7 {1984),

Google Scholar

[31]

Seidenberg, M., Tanenhaus, M. Leiman, Jr., and Bienkowski, M. Automatic access of the meaning of ambiguous words in context: Some limitations of knowledge-based processing. Cog. Psy. 14, 4 (1982), 489-537.{

Google Scholar

[32]

Tomita, M. Efficient Parsing for Natural Language. Kluwer Academic Publishers, Norwell, Mass., 1987.

Digital Library

Google Scholar

[33]

Wanner, E. The ATN and the sausage machine: Which one is baloney? Cog. 8 (1980), 209-225.

Crossref

Google Scholar

[34]

Woods, W. Transition network grammars for natural language analysis. Commun. ACM 13, 10 {Oct. 1970), 591-606.

Digital Library

Google Scholar

[35]

Yngve, V. A model and an hypothesis for language structure. In Proceedings of the American Philosophical Society 104 (1960), 444-466.

Google Scholar

Cited By

View all

유덕근 (2012)Modulare Sprachverarbeitung und InkrementalitätKoreanische Zeitschrift für Germanistik10.31064/kogerm.2012.53.1.14553:1(145-171)Online publication date: Mar-2012
https://doi.org/10.31064/kogerm.2012.53.1.145
Cohen-Sygal YWintner S(2006)Finite-State Registered Automata for Non-Concatenative MorphologyComputational Linguistics10.1162/coli.2006.32.1.4932:1(49-82)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1162/coli.2006.32.1.49
Piastra MBolognesi R(2005)An efficient context-free parsing algorithm with semantic actionsTrends in Artificial Intelligence10.1007/3-540-54712-6_239(271-280)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-54712-6_239
Show More Cited By

Index Terms

A finite and real-time processor for natural language

Recommendations

The formal definition of a real-time language

This paper presents the formal definition of TOMAL (Task-Oriented Microprocessor Applications Language), a programming language intended for real-time systems running on small processors. The formal definition addresses all aspects of the language. ...
On the Relationship between a Computational Natural Logic and Natural Language
ICAART 2016: Proceedings of the 8th International Conference on Agents and Artificial Intelligence

This paper makes a case for adopting appropriate forms of natural logic as target language for computational

reasoning with descriptive natural language. Natural logics are stylized fragments of natural language

where reasoning can be conducted directly ...
Route description using natural language generation technology
AIRS'08: Proceedings of the 4th Asia information retrieval conference on Information retrieval technology

This paper aims to solve the problems of generating natural language route description in Chinese way-finding systems, on the basis of datasets of geographical information systems and natural language generation technology. The techniques of deriving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 32, Issue 10

Oct. 1989

101 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/67933

Editor:
Peter J. Denning
NASA Ames Reseach Center, Moffett Field, CA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1989

Published in CACM Volume 32, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
520
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)20

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

유덕근 (2012)Modulare Sprachverarbeitung und InkrementalitätKoreanische Zeitschrift für Germanistik10.31064/kogerm.2012.53.1.14553:1(145-171)Online publication date: Mar-2012
https://doi.org/10.31064/kogerm.2012.53.1.145
Cohen-Sygal YWintner S(2006)Finite-State Registered Automata for Non-Concatenative MorphologyComputational Linguistics10.1162/coli.2006.32.1.4932:1(49-82)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1162/coli.2006.32.1.49
Piastra MBolognesi R(2005)An efficient context-free parsing algorithm with semantic actionsTrends in Artificial Intelligence10.1007/3-540-54712-6_239(271-280)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-54712-6_239
Chan S(2004)Extraction of salient textual patternsIEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans10.1109/TSMCA.2003.82057034:2(205-218)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1109/TSMCA.2003.820570
Manaris B(1998)Natural Language Processing: A Human-Computer Interaction Perspective10.1016/S0065-2458(08)60665-8(1-66)Online publication date: 1998
https://doi.org/10.1016/S0065-2458(08)60665-8
Lombardo V(1998)A Computational Model of RecoveryReanalysis in Sentence Processing10.1007/978-94-015-9070-9_9(287-325)Online publication date: 1998
https://doi.org/10.1007/978-94-015-9070-9_9
Lewis R(1998)Reanalysis and Limited Repair Parsing: Leaping off the Garden PathReanalysis in Sentence Processing10.1007/978-94-015-9070-9_8(247-285)Online publication date: 1998
https://doi.org/10.1007/978-94-015-9070-9_8
Abney S(1996)Partial parsing via finite-state cascadesNatural Language Engineering10.1017/S13513249970015992:4(337-344)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1017/S1351324997001599
Taira RJohnson DBhushan VRivera MWong CHuang LAberle DGreaves MGoldin J(1996)A concept-based retrieval system for thoracic radiologyJournal of Digital Imaging10.1007/BF031685659:1(25-36)Online publication date: Feb-1996
https://doi.org/10.1007/BF03168565
Lewis R(1996)Interference in short-term memory: The magical number two (or three) in sentence processingJournal of Psycholinguistic Research10.1007/BF0170842125:1(93-115)Online publication date: Jan-1996
https://doi.org/10.1007/BF01708421
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

The formal definition of a real-time language

On the Relationship between a Computational Natural Logic and Natural Language

Route description using natural language generation technology

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations