Article (Scientific journals)
Decidability of difference logics with unary predicates
Boigelot, Bernard; Fontaine, Pascal; Vergain, Baptiste
2023In CEUR Workshop Proceedings, 3458, p. 25-36
Peer Reviewed verified by ORBi
 

Files


Full Text
2022_scsc_paper.pdf
Author preprint (332.62 kB) Creative Commons License - Attribution
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Satisfiability; First-order logic; Unary uninterpreted predicates; Difference logic
Abstract :
[en] We investigate the decidability of a family of logics mixing difference-logic constraints and unary uninterpreted predicates. The focus is set on logics whose domain of interpretation is R, but the language has a recognizer for integer values. We first establish the decidability of the logic allowing unary uninterpreted predicates, order constraints between real and integer variables, and difference-logic constraints between integer variables. Afterwards, we prove the undecidability of the logic where unary uninterpreted predicates and difference-logic constraints between real variables are allowed.
Disciplines :
Computer science
Author, co-author :
Boigelot, Bernard  ;  Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Informatique
Fontaine, Pascal  ;  Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Systèmes informatiques distribués
Vergain, Baptiste  ;  Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Systèmes informatiques distribués
Language :
English
Title :
Decidability of difference logics with unary predicates
Publication date :
19 August 2023
Journal title :
CEUR Workshop Proceedings
eISSN :
1613-0073
Publisher :
RWTH Aachen University, Aachen, Germany
Volume :
3458
Pages :
25-36
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 13 November 2023

Statistics


Number of views
32 (0 by ULiège)
Number of downloads
41 (3 by ULiège)

Scopus citations®
 
0
Scopus citations®
without self-citations
0

Bibliography


Similar publications



Contact ORBi