CoChat
Sign Up
Cited by 1,357Speech Recognition and SynthesisSpeech and dialogue systemsNatural Language Processing Techniques

The Hearsay-II Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty

Open access
Erman, Lee D., Hayes-Roth, Frederick, Lesser, Victor R., Reddy, D. Raj·1980·ACM Computing Surveys
DOI 10.1145/356810.356816
Open this paper in CoChat — free accountOpen PDF

Abstract

The Hearsay-II system, developed during the DARPA-sponsored five-year speechunderstanding research program, represents both a specific solution to the speechunderstanding problem and a general framework for coordinating independent processes to achieve cooperative problem-solving behavior.As a computational problem, speech understanding reflects a large number of intrinsically interesting issues.Spoken sounds are achieved by a long chain of successive transformations, from intentions, through semantm and syntactic structurmg, to the eventually resulting audible acoustic waves.As a consequence, interpreting speech means effectively inverting these transformations to recover the speaker's intention from the sound.At each step in the interpretive process, ambiguity and uncertainty arise.The Hearsay-II problem-solving framework reconstructs an intention from hypothetmal interpretations formulated at various levels of abstraction.In additmn, it allocates hmlted processing resources fwst to the most promising incremental actions.The final configuration of the Hearsay-II system comprises problem-solving components to generate and evaluate speech hypotheses, and a focus-of-control mechanism to identify potentml actions of greatest value.Many of these specific procedures reveal novel approaches to speech problems.Most important, the system successfully integrates and coordinates all of these independent actlwhes to resolve uncertainty and control combmatorms.Several adaptations of the Hearsay-II framework have already been undertaken in other problem domains, and it is anticipated that this trend will contmue; many future systems necessarily will integrate diverse sources of knowledge to solve complex problems cooperatively.Discussed m this paper are the characteristics of the speech problem in particular, the specml kinds of problem-solving uncertainty in that domain, the structure of the Hearsay-II system developed to cope with that uncertamty, and the relationship between Hearsay-Irs structure and those of other speech-understanding systems.The paper is intended for the general computer science audience and presupposes no speech or artificial intelligence background.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/356810.356816

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Prior shared-state coordination approaches (Linda, blackboards, stigmergy) coordinate via observation but lack formal guarantees for deterministic convergence under concurrent writes, application to LLM agents, and empirical characterization across diverse task structures.

    “These approaches coordinate via observation but lack: (1) formal guarantees for deterministic convergence under concurrent writes (Linda uses locking, blackboards use centralized serialization, stigmergy is best-effort), (2) application to LLM agents with stochastic behavior and semantic reasoning, (3) empirical characterization of performance across diverse task structures.”

    From CodeCRDT: Observation-Driven Coordination for Multi-Agent LLM Code Generation (2025) · cites this paper as Erman et al., 1980

    Split into 2 atoms — 0 confirmed, 2 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

  • Observation-driven coordination is a decades-old pattern from distributed systems (Linda tuplespaces, blackboard architectures, stigmergy).

    “We apply observation-driven coordination -a decades-old pattern from distributed systems (Linda tuplespaces (Gelernter, 1985), blackboard architectures (Erman et al., 1980), stigmergy (Theraulaz & Bonabeau, 1999))”

    From CodeCRDT: Observation-Driven Coordination for Multi-Agent LLM Code Generation (2025) · cites this paper as Erman et al., 1980

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 59

  1. ARBIB, M A, AND CAPLAN, D. "Neuro- hnguistics must be computational," Be. hay. Bram Sct. 2, 3 (1979).
  2. BAHL, L. R., BAKER, J K., COHEN, P S., DIXON, N. R., JELINEK, F., MERCER, R. L., AND SILVERMAN, H.F. "Preliminary results on the performance of a system for the automatm recognition of continuous speech," in 1976 IEEE Int Conf. Aeous. tics, Speech, and Signal Processmg, Phil- adelphia, Apr. 1976, pp. 425-433
  3. BAHL, L. R., BAKER, J. K., COHEN, P. S., COLE, A. G, JELINEK, F., LEWIS, B. L., AND MERCER, R.L. "Automatw recog- nition of continuously spoken sentences from a fimte state grammar," m Proc. IEEE Int. Conf Acousttcs, Speech, and Signal Processmg, Tulsa, Okla., Apr. 1978, pp. 418-421.
  4. BURTON, R. R Semantw grammar. An engtneermg techntque for constructtng natural language understandmg systems, Tech Rep BBN Rep. No. 3453, Bolt Ber- anek and Newman, Cambridge, Mass, 1976.
  5. DUDA, R. O, HART, P. E, NILSSON, N. J., AND SOUTHERLAND, G. L. "Semantic network representation in rule-based in- ference systems," in Pattern-dwected re- ference systems, D. A. Waterman and F. Hayes-Roth, Eds., Academic Press, New York, 1978, pp. 203-222.
  6. ERMAN L. D., AND LESSER, V. R. "A multi-level organization for problem solv- mg using many diverse cooperating sources of knowledge," m Proc. 4th Int. Jt. Conf. Artlficml Intelhgence, Tbflisi, USSR, 1975, pp. 483-490
  7. ERMAN, L. D., AND LESSER, V R. "Sys- tem engmeermg techniques for arhficml mtelhgence systems," in Computer wsmn systems, A. Hanson and E. Riseman, Eds., Academic Press, New York, 1978, pp. 37- 45.
  8. ERNST, G, AND NEWELL, A. GPS: A case study tn generahty and problem solv- ing, Academic Press, New York, 1969.
  9. FEIGENBAUM, E A, BUCHANAN, B. G., AND LEDERBERG, J. "On generality and problem solving' A case study using the DENDRAL program," in Machine intel- hgence 6, D. Michie, Ed, Edinburgh Univ Press, Edinburgh, Scotland, 1971.
  10. FEIGENBAUM, E. A "The art of artlficml intelligence: Themes and case studies of knowledge engineering," in Proc. 5th Int.
  11. Jt. Conf Arttf~cml Intelhgence, Cam- bridge, Mass., 1977, pp. 1014-1029.
  12. Fox, M. S., AND MOSTOW, D.J. "Maxi- mal consistent interpretatmns of errorful data in hierarchically modelled domains," in Proc 5th Int Jt Conf. Art~ficml Intel- hgence, Cambridge, Mass., 1977, pp 65- 171.
  13. Fox, M. S. "An organizational wew of dmtnbuted systems," m Proc. Int. Conf. Systems and Cybernetzcs, Denver, Colo., Oct. 1979.
  14. GOLDBERG, H., REDDY, R., AND GILL, G "The ZAPDASH parameters, feature ex- traction, segmentation, and labeling for speech understanding systems," in CMU77, pp. 10-11.
  15. HARRIS, L.R. "The heuristic search un- der conditions of error," Artif. Intell. 5, 3 (1974), 217-234
  16. HAYES-ROTH, F., AND MOSTOW, D J. "An automatically compilable recogmtion network for structured patterns," m Proc. 4th Int Jt. Conf. Artificial Intelhgence, Tbihsl, USSR, 1975, pp. 246-252.
  17. HAYES-ROTH, F., AND LESSER, V. R. "Focus of attention in the Hearsay-II sys- tem," m Proc. 5th Int. Jt. Conf Artificml Intelhgence, Cambridge, Mass., 1977, pp. 27-35.
  18. HAYES-ROTH, F., GILL, G., AND MOSTOW, D.J. "Discourse analysis and task per- formance in the Hearsay-II speech under- standing system," in CMU77, pp. 24-28.
  19. HAYES-ROTH, F., LESSER, V. R., MOSTOW, D. J., AND ERMAN, L. D. "Policies for rating hypotheses, halting, and selecting a solution in Hearsay-II," in CMU77, pp. 19-24
  20. HAYES-ROTH, F., WATERMAN, D. A., AND LENAT, D.B. "Principles of pattern-di- rected inference systems," in Pattern.d~- reeted reference systems, D. A. Waterman and F. Hayes-Roth, Eds., Academic Press, New York, 1978.
  21. HAYES-ROTH, F. "The role of partial and best matches m knowledge systems," m Pattern-dwected inference systems, D. A. Waterman and F. Hayes-Roth, Eds., Aca- demic Press, New York, 1978.
  22. HAYES-ROTH, B., AND HAYES-ROTH, F. "A cognitive model of planning," Cogni. twe Sci 3 (1979), 275-310.
  23. HAYE80 ITAK75 KLAT77 LEA79 LEA80 LESS75 o Conf. Artlficial Intelligence, Tokyo, 1979, pp. 375-383.
  24. ITAKURA, F. "Mimmum prediction resid- ual principle applied to speech recogni- tion," IEEE Trans. Acoust., Speech, Sig. hal Proc. 23 (1975), 67-72.
  25. KLATT, D. H. "Review of the ARPA speech understanding project," d. Acoust. Soc. Am. 62 (Dec. 1977), 1345-1366.
  26. LESSER, V. R., FENNELL, R. D., ERMAN, L. D., AND REDDY, D.R. "Organizatmn of the Hearsay-II speech understanding NEWE73 system," IEEE Trans. Acous., Speech, Signal Proe. 23 (1975), 11-23.
  27. LEss77a LESSER, V. R., HAYES-ROTH, F., BIRN- DAUM, M., AND CI~ONK, R. "Selection of word islands in the Hearsay-IT speech un- derstanding system," in Proc. IEEE Int. Conf. Acoustics, Speech, and Stgnal Pro- cessing, Hartford, Conn., 1977, pp. 791- 794.
  28. LEss77b LESSER, V. R., AND ERMAN, L. D. "A retrospective view of the Hearsay-II ar- chitecture," m Proc. 5th Int. Joint Conf. Artificial Intelligence, Cambridge, Mass., 1977, pp. 790-800.
  29. LESS79 LESSER, V. R., AND ERMAN, L. D "An experiment in distributed interpretatmn," m 1st Int. Conf D~str~buted Computing Systems, IEEE Computer Society, Hunts- vflle, Ala., Oct 1979, pp. 553-571.
  30. LEVI78 LEVlNE, M. D. "A knowledge-based NII79 computer vision system," in Computer vt- sion systems, A. Hanson and E. Riseman, Eds,, Academic Press, New York, 1978, pp. 335-352.
  31. LOWE76 LOWZRRE, B. T The HARPY speech recognttton system, Ph.D. thesis, Corn-NILS71 puter Science Dep., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976.
  32. LowRS0 LOWRANCE, J. Dependence-graph models POHL70 of evidential support, Ph.D. thesis, Dep Comlmting Surveys, Vol. 12, No. 2, June 1980
  33. McKEoWN, D.M. "Word verification in the Hearsay-II speech understanding sys- tem," m Proc. IEEE Int. Conf Acoustics, Speech, and Stgnal Processing, Hartford, Conn., 1977, pp. 795-798.
  34. MEDRESS, M. F., COOPER, F. S., FORGIE, J. W., GREEN, C. C., KLATT, D. H., O'MALLEY, M. H., NEUBURG, E. P., NEW- ELL, A., REDDY, D. R., RITEA, B., SHOUP- HUMMEL, J. E., WALKER, D. E., AND WOODS, W. A. "Speech understandmg systems: Report of a steering committee," Art~f. Intell. 9 (1978), 307-316.
  35. MOSTOW, D.J. "A halting condition and related pruning heuristic for combinatorial search," in CMU77, pp. 158-166.
  36. NEWELL, A. "Heuristic programming: Ill-structured problems," in Progress m operatmns research 3, J. Aronofsky, Ed., Wiley, New York, 1969, pp. 360-414.
  37. NEWELL, A, "A tutorial on speech un- derstanding systems," in Speech recogn~. tmn: Inwted papers of the IEEE sympo- sium, D. R. Reddy, Ed., Academic Press, New York, 1975, pp. 3-54
  38. NEWELL, A. "HARPY, production sys- tems and human cognition," in Perceptmn and production of fluent speech, R. Cole, Ed., L. Erlbaum, Hdlsdale, N.J., 1980, Chap. 11. Nil, H. P., AND FEIGENBAUM, E A. "Rule-based understanding of signals," in Pattern.dweeted znference systems, D. A. Waterman and F. Hayes-Roth, Eds., Aca- demic Press, New York, 1978.
  39. NII, H. P., AND AIELLO, N. "AGE (At- tempt to Generalize). A knowledge-based program for braiding knowledge-based programs," in Proc. 6th Int. Jt. Conf. Ar. ttficial Intelligence, Tokyo, Feb. 1979, pp. 645-655.
  40. NILSSON, N. Problem-solwng methods ~n artificial mtelhgence, McGraw-Hill, New York, 1971
  41. REDD73a REDD73b REDD75 REDD76 REIS76 RUBI78 RUME76 SACE74 SHOR75 SHOR76 SMIT76 SMIT77 RECEIVED Hearsay-H Speech-Understanding System telhgence 5, B. Meltzer and D Mmhm, Eds, Edinburgh Umv Press, Edinburgh, SMIT81 Scotland, 1970
  42. REDDY, D. R., ERMAN, L. D., AND NEELY, R B "A model and a system for machine recogmtmn of speech," IEEE Trans Au- dio and Electroacousttcs AU-21 (1973), SOND78 229-238.
  43. REDDY, D. R., ERMAN, L. D., FENNELL, R. D, AND NEELY, R. B. "The Hearsay speech understanding system An example of the recognitmn process," m Proc. 3rd Int. Jr. Conf. Artificial Intelhgence, Stan- STEF80 ford, Calif., 1973, pp. 185-193.
  44. REDDY, D. R, ED Speech recognition" Inwted papers presented at the 1974 WALK78 IEEE Symposium, Academic Press, New York, 1975
  45. REDDY, D. R. "Speech recogmtlon by WALK80 machine: A rewew," Proc IEEE 64 (Apr. 1976), 501-531.
  46. RUBIN, S. The ARGOS ~mage under- standing system, Ph D. thesis, Computer Scmnce Dep., Carnegm-Mellon Umv, Pittsburgh, Pa., 1978.
  47. SACERDOTI, E.E. "Planmng in a hmrar- chy of abstractmn spaces," Art~f Intell 5 (1974), 115-135.
  48. SHORTLIFFE, E. H, AND BUCHANAN, B. G. "A model of inexact reasomng m med- icine," Math Bin. Sc~. 23 (1975) WOOD76 SHORTLIFFE, E Computer-based medi- cal consultatmn MYCIN, Elsevier, New York, 1976
  49. SMITH, A.R. "Word hypotheslzatmn in the Hearsay-II speech system," m Proc. IEEE Int Conf Acoustzcs, Speech, and Signal Processing, Phlladelphm, Pa., 1976, pp. 549-552.
  50. SMITH, A.R. Word hypothestzatton for large-vocabulary speech understandmg systems, Ph D. thesis, Computer Science Dep, Carnegie-Mellon Umv., Pittsburgh, • 253
  51. SMITH, A. R., AND ERMAN, L. D. "NOAH: A bottom-up word hypotheslzer for large-vocabulary speech-understand- ing systems," IEEE Trans. Pattern Anal.
  52. SOLOWAY, E. M., AND RISEMAN, E M. "Levels of pattern description in learning," in Proc 5th Int. J. Conf. Artificial Intel- hgence, Cambridge, Mass., 1977, pp 801- 811
  53. SONDHI, M. M., AND LEVINSON, S E "Computing relative redundancy to mea- sure grammatical constraint in speech rec- ogmtlon tasks," in Proc. IEEE Int Conf Acoustics, Speech, and S~gnal Process- rag, Tulsa, Okla., Apr. 1978.
  54. STEFIK, M. Planning w~th constraints, Ph.D thesis, Computer Scmnce Dep., Stanford Univ., Stanford, Cahf., Jan. 1980.
  55. WALKER, D. E., ED. Understanding spo- ken language, Elsevier North-Holland, New York, 1978.
  56. WOODS, W A. "Transition network grammars for natural language analysis," Commun ACM 13, 10 (Oct. 1970), 591- 606
  57. WOODS, W. A., AND MAKHOUL, J. "Mechanical inference problems in contin- uous speech understanding," in Proc 3rd Int. Jt. Conf Artificial Intelligence, Stan- ford, Calif., 1973, pp 73-91, also Arttf Intell. 5, 1 (Spring 1974), 73-91.
  58. WOODS, W., BATES, M., BROWN, G., BRUCE, B., COOK, C, KLOVSTAD, J, MAK- HOUL, J., NASH-WEBBER, B., SCHWARTZ, R, WOLF, J, AND ZUE, V. Speech under. standzng systems: Final technical prog- ress report, Tech Rep 3438, Bolt Beranek and Newman, Cambridge, Mass., Dec. 1976 (in 5ve volumes).
  59. WOODS, W. A. "Shortfall and density scoring strategies for speech understand- ing control," In Proc. 5th Int. Jt. Conf Artificial Intelligence, Cambmdge, Mass., 1977, pp. 13-26. AUGUST 1979, FINAL REVISION ACCEPTED FEBRUARY 1980 Computing Surveys, Vol. 12, No. 2, June 1980

Cited by

Sorted by citations

Authors
Erman, L. D., Hayes-Roth, F., Lesser, V. R., & Reddy, D. R.
Affiliations
  • University of Southern California (US)
  • RAND Corporation (US)
  • University of Massachusetts Amherst (US)
  • Carnegie Mellon University (US)
Venue
ACM Computing Surveys
Publisher
Association for Computing Machinery (ACM)
Published
1980-06
Volume
12
Issue
2
Pages
213-253
ISSN
  • 0360-0300 (ISSN-L)
  • 1557-7341
DOI
10.1145/356810.356816
OpenAlex
W2051768896
Cited by
1,357
References
0
Citations by year
2026: 17 · 2025: 27 · 2024: 9 · 2023: 4 · 2022: 5 · 2021: 11 · 2020: 9 · 2019: 9 · 2018: 24 · 2017: 12 · 2016: 17 · 2015: 19 · 2014: 20 · 2013: 17 · 2012: 19
FWCI
42.04
Type
journal article
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
ACM Computing Surveys (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Speech Recognition and Synthesis
  • Physical Sciences › Computer Science › Artificial Intelligence › Speech and dialogue systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
Keywords
speech understanding, uncertainty resolution, knowledge integration, collaborative problem solving, resource allocation, ambiguity

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