Decidability of the Monadic Shallow Linear First-Order Fragment with Straight 
Dismatching Constraints

Teucke, Andreas; Weidenbach, Christoph

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

前へ次へ / 131

公開

成果報告書

Decidability of the Monadic Shallow Linear First-Order Fragment with Straight Dismatching Constraints

MPS-Authors

/persons/resource/persons127656

Teucke, Andreas
Automation of Logic, MPI for Informatics, Max Planck Society;

/persons/resource/persons45719

Weidenbach, Christoph
Automation of Logic, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1703.02837.pdf
(プレプリント), 305KB

付随資料 (公開)

There is no public supplementary material available

引用

Teucke, A., & Weidenbach, C. (2017). Decidability of the Monadic Shallow Linear First-Order Fragment with Straight Dismatching Constraints. Retrieved from http://arxiv.org/abs/1703.02837.

引用: https://hdl.handle.net/11858/00-001M-0000-002C-A213-1

要旨

The monadic shallow linear Horn fragment is well-known to be decidable and has many application, e.g., in security protocol analysis, tree automata, or abstraction refinement. It was a long standing open problem how to extend the fragment to the non-Horn case, preserving decidability, that would, e.g., enable to express non-determinism in protocols. We prove decidability of the non-Horn monadic shallow linear fragment via ordered resolution further extended with dismatching constraints and discuss some applications of the new decidable fragment.