バックトラッキング
バックトラッキングの最も広範囲な利用法として、正規表現の実行がある。例えば、"a*a" という単純なパターンはバックトラッキングしない場合に "a" にマッチしない(最初のパスで "a" が "a*" に食われてしまい、後続の "a" にはマッチさせるべき文字列が残らないため)。
バックトラッキングはプログラミング言語の実装にも使われている(Planner や Prolog)し、構文解析などにも利用される。その利用は人工知能分野で議論となり、アクターモデルの開発につながった。