de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

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

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons127656

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45719

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1703.02837.pdf
(Preprint), 305KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-002C-A213-1
Zusammenfassung
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.