A Polynomial Translation from the Two-Variable Guarded Fragment with Number 
Restrictions to the Guarded Fragment

Kazakov, Yevgeny; Alferes, José Júlio; Leite, João

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded Fragment

MPS-Authors

/persons/resource/persons44749

Kazakov, Yevgeny
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

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

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Kazakov, Y. (2004). A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded Fragment. In Logics in artificial intelligence: 9th European Conference, JELIA 2004 (pp. 372-384). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2A28-6

Abstract

We consider a two-variable guarded fragment with number restrictions for binary relations and give a satisfiability preserving transformation of formulas in this fragment to the three-variable guarded fragment. The translation can be computed in polynomial time and produces a formula that is linear in the size of the initial formula even for the binary coding of number restrictions. This allows one to reduce reasoning problems for many description logics to the satisfiability problem for the guarded fragment.