Pruning state spaces with extended beam search

M. Torabi Dashti, A.J. Wijs

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

This paper focuses on using beam search, a heuristic search algorithm, for pruning state spaces while generating. The original beam search is adapted to the state space generation setting and two new search variants are devised. The resulting framework encompasses some known algorithms, such as A*. We also report on two case studies based on an implementation of beam search in mCRL.
Original languageEnglish
Title of host publicationProceedings of the 5th International Symposium of Automated Technology for Verification and Analysis
EditorsK.S. Namjoshi
Place of PublicationHeidelberg
PublisherSpringer
Pages543-552
ISBN (Print)978-3-540-75596-8
DOIs
Publication statusPublished - 2007

Publication series

NameLecture Notes in Computer Science
Volume4762
ISSN (Print)0302-9743

Cite this