- Journal article

Bolotov, A., Hermo, M. and Lucio, P. 2020. Branching-time logic ECTL# and its tree-style one-pass tableau: Extending fairness expressibility of ECTL+. *Theoretical Computer Science.* 813, pp. 428-451. doi:10.1016/j.tcs.2020.02.015.

Title | Branching-time logic ECTL# and its tree-style one-pass tableau: Extending fairness expressibility of ECTL+ |
---|---|

Type | Journal article |

Authors | Bolotov, A. |

Hermo, M. | |

Lucio, P. | |

Abstract | Temporal logic has become essential for various areas in computer science, most notably for the specification and verification of hardware and software systems. For the specification purposes rich temporal languages are required that, in particular, can express fairness constraints. For linear-time logics which deal with fairness in the linear-time setting, one-pass and two-pass tableau methods have been developed. In the repository of the CTL-type branching-time setting, the well-known logics ECTL and ECTL+ were developed to explicitly deal with fairness. However, due to the syntactical restrictions, these logics can only express restricted versions of fairness. The logic CTL⋆, often considered as ‘the full branching-time logic’ overcomes these restrictions on expressing fairness. However, CTL⋆ is extremely challenging for the application of verification techniques, and the tableau technique, in particular. For example, there is no one-pass tableau construction for CTL⋆, while one-pass tableau has an additional benefit enabling the formulation of dual sequent calculi that are often treated as more ‘natural’ being more friendly for human understanding. These two considerations lead to the following problem - are there logics that have richer expressiveness than ECTL+, allowing the formulation of a new range of fairness constraints with ‘until’ operator, yet ‘simpler’ than CTL⋆, and for which a one-pass tableau can be developed? Here we give a positive answer to this question, introducing a sub-logic of CTL⋆ called ECTL#, its tree-style one-pass tableau, and an algorithm for obtaining a systematic tableau, for any given admissible branching-time formulae. We prove the termination, soundness and completeness of the method. As tree-shaped one-pass tableaux are well suited for the automation and are amenable for the implementation and for the formulation of sequent calculi. Our results also open a prospect of relevant developments of the automation and implementation of the tableau method for ECTL#, and of a dual sequent calculi. |

Keywords | Temporal logic; Fairness; Tableau; Branching-time; One-pass tableau |

Journal | Theoretical Computer Science |

Journal citation | 813, pp. 428-451 |

ISSN | 0304-3975 |

Year | 2020 |

Publisher | Elsevier |

Digital Object Identifier (DOI) | doi:10.1016/j.tcs.2020.02.015. |

Publication dates | |

Published | 13 Feb 2020 |

One-pass Context-based Tableaux Systems for CTL and ECTL

Bolotov, A., Lucio, P., Hermo, M. and Alex Abuin 2020. One-pass Context-based Tableaux Systems for CTL and ECTL. *27th International Symposium on Temporal Representation and Reasoning.* Bozen-Bolzano, Italy 23 - 25 Sep 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany.

Science Gateways with Embedded Ontology-based E-learning Support

Kiss, T., Bolotov, A., Pierantoni, G., Deslauriers, J., MOSA, A., Kagialis, D., Terstyanszky, G. and Chan, D.Y.L. 2020. Science Gateways with Embedded Ontology-based E-learning Support. Gesing, S., Taylor, I. and Barclay, I (ed.) *12th International Workshop on Science Gateways.* On-line 10 - 11 Jun 2020 CEUR Workshop Proceedings.

Semantic Data Pre-Processing for Machine Learning Based Bankruptcy Prediction Computational Model

Yerashenia, N., Bolotov, A., Chan You Fee, D. and Pierantoni, G. 2020. Semantic Data Pre-Processing for Machine Learning Based Bankruptcy Prediction Computational Model. *22nd IEEE International Conference on Business Informatics (IEEE CBI 2020) .* Antwerp, Belgium 22 - 24 Jun 2020 IEEE . doi:10.1109/CBI49978.2020.00015

Proceedings of the Automated Reasoning Workshop (ARW 2019)

Bolotov, A. and Kammueller, F. 2019. *Proceedings of the Automated Reasoning Workshop (ARW 2019).* London

Creating an Intelligent System for Bankruptcy Detection: Semantic data Analysis Integrating Graph Database and Financial Ontology

Yerashenia, N. and Bolotov, A. 2019. Creating an Intelligent System for Bankruptcy Detection: Semantic data Analysis Integrating Graph Database and Financial Ontology. *Automated Reasoning Workshop 2019: Bridging the Gap between Theory and Practice.* University of Middlesex 02 - 03 Sep 2019 Middlesex University.

Towards Certified Model Checking for PLTL using One-pass Tableaux

Abuin, A., Bolotov, A., de Cerio, U., Hermo, M. and Lucio, P. 2019. Towards Certified Model Checking for PLTL using One-pass Tableaux. *26th International Symposium on Temporal Representation and Reasoning, TIME 2019.* Malaga, Spain 16 - 19 Oct 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. doi:10.4230/LIPIcs.TIME.2019.12

Computational Modelling for Bankruptcy Prediction: Semantic data Analysis Integrating Graph Database and Financial Ontology

Yerashenia, N. and Bolotov, A. 2019. Computational Modelling for Bankruptcy Prediction: Semantic data Analysis Integrating Graph Database and Financial Ontology. *21st IEEE Conference on Business Informatics.* Moscow, Russian Federation 15 - 17 Jul 2019 IEEE . doi:10.1109/CBI.2019.00017

EnAbled: A Psychology Profile based Academic Compass to Build and Navigate Students' Learning Paths

Bolotov, A., Chan, D.Y.L., Pierantoni, G., Wisudha, A. and Abduraimova, Z. 2018. EnAbled: A Psychology Profile based Academic Compass to Build and Navigate Students' Learning Paths. *EC-TEL Practitioner Proceedings 2018: 13th European Conference On Technology Enhanced Learning.* Leeds, UK 03 - 06 Sep 2018 CEUR.

Extending fairness expressibility of ECTL+: a tree-style one-pass tableau approach

Bolotov, A., Hermo, M. and Lucio, P. 2018. Extending fairness expressibility of ECTL+: a tree-style one-pass tableau approach. *25th International Symposium on Temporal Representation and Reasoning, TIME-2018.* Warsaw, Poland 15 - 17 Oct 2018 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.TIME.2018.5

Enabled: Educational Network Amplifying Learning Experience (EnAbled)

Bolotov, A., Pierantoni, G., Wisudha, A., Abduraimova, Z. and Chan You Fee, D. 2018. *Enabled: Educational Network Amplifying Learning Experience (EnAbled).*

Paracomplete logic Kl: natural deduction, its automation, complexity and applications

Bolotov, A., Kozhemiachenko, D. and Shangin, V. 2018. Paracomplete logic Kl: natural deduction, its automation, complexity and applications. *Journal of Applied Logics - IfCoLog Journal of Logics and their Applications.* 5 (1), pp. 221-261.

On the Complexity of the Natural Deduction Proof Search Algorithm

Bolotov, A., Shangin, V. and Kozhemiachenko, D. 2017. On the Complexity of the Natural Deduction Proof Search Algorithm. *ARW2017 - 24th Automated Reasoning Workshop.* Bristol 03 - 04 Apr 2017 University of Bristol Technical Report.

Towards Generalised Proof Search for Natural Deduction Systems for logics I⟨a;b⟩

Bolotov, A. and Shangin, V. 2016. Towards Generalised Proof Search for Natural Deduction Systems for logics I⟨a;b⟩. Hustadt, U. (ed.) *Automated Reasoning Workshop 2016: Bridging the Gap between Theory and Practice (ARW 2016).* Liverpool 19 - 20 May 2016 Automated Reasoning Workshop.

Discovering of System’s Invariants by Temporal Reasoning

Bolotov, A. 2016. Discovering of System’s Invariants by Temporal Reasoning. *The International Conference on Innovations in Info-business and Technology (ICIIT).* Colombo, Sri Lanka 04 - 04 Mar 2016 Informatics Institute of Technology.

Sensor Intelligence for Tackling Energy-Drain Attacks on Wireless Sensor Networks

Udoh, E., Getov, Vladimir and Bolotov, A. 2016. Sensor Intelligence for Tackling Energy-Drain Attacks on Wireless Sensor Networks. *The 23rd Workshop on Automated Reasoning: Bridging the Gap between Theory and Practice.* University of Liverpool 19 - 20 May 2016 Automated Reasoning Workshop.

Distributed Agent-Based Load Balancer for Cloud Computing

Sliwko, L., Getov, Vladimir and Bolotov, A. 2015. Distributed Agent-Based Load Balancer for Cloud Computing. *The 22nd Workshop on Automated Reasoning: Bridging the Gap between Theory and Practice.* University of Birmingham 09 Apr 2015 Automated Reasoning Workshop.

Socratic Proofs for Propositional Linear-Time Logic

Urbanski, M., Bolotov, A., Shangin, V. and Grigoriev, O. 2014. Socratic Proofs for Propositional Linear-Time Logic. Bolotov, A. (ed.) *Joint Automated Reasoning Workshop and Deduktionstreffen.* Vienna 23 - 24 Jul 2014 IJCAR.

Tackling Incomplete System Specifcations Using Natural Deduction in the Paracomplete Setting

Bolotov, A. and Shangin, V. 2014. Tackling Incomplete System Specifcations Using Natural Deduction in the Paracomplete Setting. * COMPSAC 2014.* Vasteras, Sweden Jul 2014 IEEE . doi:10.1109/COMPSAC.2014.15

Natural Deduction in a Paracomplete Setting

Bolotov, A. and Shangin, V. 2014. Natural Deduction in a Paracomplete Setting. *Logical Investigations.* 20, pp. 224-247.

Natural deduction system in paraconsistent setting: proof search for PCont

Bolotov, A. and Shangin, V. 2012. Natural deduction system in paraconsistent setting: proof search for PCont. *Journal of Intelligent Systems.* 21 (1), pp. 1-24. doi:10.1515/jisys-2011-0021

Natural deduction system in paraconsistent setting: proof search for PCont

Bolotov, A. and Shangin, V. 2011. Natural deduction system in paraconsistent setting: proof search for PCont. *In the Proceedings of the 5th Indian International Conference on Artificial Intelligence (IICAI-2011).* Tumkur, Karnataka State, India 14th - 16th December 2011 pp. 630-638

Natural deduction in the setting of paraconsistent logic

Bolotov, A. 2011. Natural deduction in the setting of paraconsistent logic. *18th Automated Reasoning Workshop 2011 (ARW2011).* University of Glasgow 11th - 12th April 2011

Handling periodic properties: deductive verification for quantified temporal logic specifications

Bolotov, A. 2011. Handling periodic properties: deductive verification for quantified temporal logic specifications. in: 2011 5th international conference on secure software integration and reliability improvement companion IEEE . pp. 179-186

Safety and liveness of component-oriented protocols: a feasibility study

Paurobally, S., Bolotov, A. and Getov, Vladimir 2010. Safety and liveness of component-oriented protocols: a feasibility study. in: Bolotov, A. (ed.) Proceedings of the automated reasoning workshop 2010: bridging the gap between theory and practice. ARW 2010 University of Westminster.

Towards symbolic reasoning from subsymbolic sensory information

Bolotov, A., Gupta, G. and Psarrou, A. 2010. Towards symbolic reasoning from subsymbolic sensory information. in: Bolotov, A. (ed.) Proceedings of the automated reasoning workshop 2010: bridging the gap between theory and practice. ARW 2010 University of Westminster.

Invariant-free deduction for CTL*: the tableau method

Bolotov, A., Gaintzarain, J. and Lucio, P. 2010. Invariant-free deduction for CTL*: the tableau method. in: Bolotov, A. (ed.) Proceedings of the automated reasoning workshop 2010: bridging the gap between theory and practice. ARW 2010 University of Westminster.

Multi-agent systems as instrumentation tools for e-business and e-society

Bolotov, A. and Maltseva, S. 2009. Multi-agent systems as instrumentation tools for e-business and e-society. *Russian Internet Week.* Moscow, Russia December 2009

Natural deduction calculus for quantified propositional linear-time temporal logic (QPTL)

Bolotov, A. and Grigoriev, O. 2009. Natural deduction calculus for quantified propositional linear-time temporal logic (QPTL). in: Hustadt, U. (ed.) Proceedings of the utomated Reasoning Workshop 2009: bridging the gap between theory and practice (ARW 2009), 21st - 22nd April 2009, , Liverpool, United Kingdon University of Liverpool Department of Computer Science.

Natural deduction calculus for quantified propositional linear-time temporal logic

Bolotov, A. and Grigoriev, O. 2009. *Natural deduction calculus for quantified propositional linear-time temporal logic.* University of Westminster.

Combining computation tree logic and deontic logic in natural deduction style calculus

Bolotov, A. and Grigoriev, O. 2009. *Combining computation tree logic and deontic logic in natural deduction style calculus.* University of Westminster.

Deontic extension of deductive verification of component model: combining computation tree logic and deontic logic in natural deduction style calculus

Bolotov, A., Basso, A. and Grigoriev, O. 2009. Deontic extension of deductive verification of component model: combining computation tree logic and deontic logic in natural deduction style calculus. in: Proceedings of the 4th Indian International Conference on Artificial Intelligence (IICAI-09), December 16-18, 2009, SIT, Tumkur, India IICAI. pp. 166-185

On the "until induction" in natural deduction for PLTL

Bolotov, A. 2009. On the "until induction" in natural deduction for PLTL. in: International conference "6th Smirnov's Readings in Logic" June 17-19, 2009, Moscow, Russia Faculty of Philosophy, Lomonosov Moscow State University.

Temporal specification and deductive verification of a distributed component model and its environment

Basso, A., Bolotov, A. and Getov, Vladimir 2009. Temporal specification and deductive verification of a distributed component model and its environment. in: Proceedings of the Third IEEE International Conference on Secure Software Integration and Reliability Improvement, 2009 (SSIRI 2009) IEEE . pp. 379-386

State-based behavior specification for GCM systems

Basso, A., Bolotov, A. and Getov, Vladimir 2009. State-based behavior specification for GCM systems. in: Hustadt, U. (ed.) Proceedings of the utomated Reasoning Workshop 2009: bridging the gap between theory and practice (ARW 2009), 21st - 22nd April 2009, , Liverpool, United Kingdon University of Liverpool Department of Computer Science.

Dynamic reconfiguration of GCM components

Basso, A., Bolotov, A., Getov, Vladimir and Henrio, L. 2008. *Dynamic reconfiguration of GCM components.* CoreGRID. doi:CoreGRIDTechnicalReportNumberTR-0173

Automating natural deduction for temporal logic

Bolotov, A., Grigoriev, O. and Shangin, V. 2008. Automating natural deduction for temporal logic. in: Glymour, C., Wang, W. and Westerstahl, D. (ed.) Proceedings of the 13th International Congress of Logic Methodology and Philosophy of Science King's College Publications.

Automating natural deduction for temporal logic

Bolotov, A., Grigoriev, O. and Shangin, V. 2008. Automating natural deduction for temporal logic. in: Proceedings of the 14th Workshop on Automated Reasoning: Bridging the Gap between Theory and Practice, ARW 2007. London Imperial College.

Natural deduction system for linear time temporal logic

Bolotov, A., Basukoski, A., Gregoryev, O. and Shangin, V. 2008. Natural deduction system for linear time temporal logic. in: Logical Investigations Moscow Nauka.

Tackling ”until induction” in natural deduction for PLTL

Bolotov, A. 2008. Tackling ”until induction” in natural deduction for PLTL. in: Dennis, L.A. and Sorge, V. (ed.) Proceedings of the automated reasoning workshop 2008 University of Birmingham. pp. 12-13

Tackling "until induction" in natural deduction for PLTL

Bolotov, A. 2008. Tackling "until induction" in natural deduction for PLTL. in: Proceedings of the 15th workshop on automated reasoning: bridging the gap between theory and practice: CICM 2008, Conferences on Intelligent Computer Mathematics, University of Birmingham, UK Birmingham School of Computer Science.

Behavioural model of component-based Grid environments

Basso, A., Bolotov, A. and Getov, Vladimir 2008. Behavioural model of component-based Grid environments. in: Priol, T. and Vanneschi, M. (ed.) From grids to service and pervasive computing Springer. pp. 19-30

Automata-based formal specification of stateful systems

Basso, A., Bolotov, A. and Getov, Vladimir 2008. Automata-based formal specification of stateful systems. in: Dennis, L.A. and Sorge, V. (ed.) Proceedings of the automated reasoning workshop 2008 University of Birmingham. pp. 6-7

Automata based formal specification of stateful systems

Basso, A., Bolotov, A. and Getov, Vladimir 2008. Automata based formal specification of stateful systems. in: Proceedings of the 15th workshop on automated reasoning: bridging the gap between theory and practice: CICM 2008, Conferences on Intelligent Computer Mathematics, University of Birmingham, UK Birmingham School of Computer Science.

Towards GCM re-configuration – extending specification by norm

Basso, A. and Bolotov, A. 2008. Towards GCM re-configuration – extending specification by norm. in: Danelutto, M., Fragopoulou, P. and Getov, Vladimir (ed.) Making grids work: Proceedings of the CoreGRID Workshop on Programming Models Grid and P2P System Architecture Grid Systems, Tools and Environments 12-13 June 2007, Heraklion, Crete, Greece New York, NY, USA Springer. pp. 17-29

A Simpler formulation of natural deduction calculus for linear-time temporal logic

Bolotov, A., Grigoriev, O. and Shangin, V. 2007. A Simpler formulation of natural deduction calculus for linear-time temporal logic. in: Bhanu, P. (ed.) Proceedings of the 3rd Indian International Conference on Artificial Intelligence, Pune, India, December 17-19, 2007. IICAI 2007 India IICAI. pp. 1253-1266

Buy one get two free: a simpler formulation of natural deduction for computation tree logic CTL

Bolotov, A., Grigoriev, O. and Shangin, V. 2007. Buy one get two free: a simpler formulation of natural deduction for computation tree logic CTL. in: Proceedings of the "Smirnov's Readings", VI International Conference (in Russian) Moscow, Russia Moscow State University.

Automating natural deduction for linear-time temporal logic

Bolotov, A., Grigoriev, O. and Shangin, V. 2007. Automating natural deduction for linear-time temporal logic. in: 14th International Symposium on Temporal Representation and Reasoning (TIME'07)), 28-30 June 2007, Alicante, Spain Los Alamitos, USA IEEE . pp. 47-58

A clausal resolution method for extended computation tree logic ECTL

Bolotov, A. and Basukoski, A. 2006. A clausal resolution method for extended computation tree logic ECTL. *Journal of Applied Logic.* 4 (2), pp. 141-167. doi:10.1016/j.jal.2005.06.003

Specification and verification of reconfiguration protocols in grid component systems

Basso, A., Bolotov, A., Basukoski, A., Getov, Vladimir, Henrio, L. and Urbanski, M. 2006. *Specification and verification of reconfiguration protocols in grid component systems.* CoreGRID. doi:CoreGRIDTechnicalReportNumberTR-0042

A clausal resolution method for branching-time logic ECTL+

Bolotov, A. and Basukoski, A. 2006. A clausal resolution method for branching-time logic ECTL+. *Annals of Mathematics and Artificial Intelligence.* 46 (3), pp. 235-263. doi:10.1007/s10472-006-9018-1

Search and Check: problem solving by problem reduction

Bolotov, A., Lupkowski, P. and Urbanski, M. 2006. Search and Check: problem solving by problem reduction. in: Artificial Intelligence and Soft Computing ICAISC 2006: 8th International Conference, Zakopane, Poland, June 25-29, 2006, Proceedings Polish Neural Networks Society.

Natural deduction calculus for computation tree logic

Bolotov, A., Grigoriev, O. and Shangin, V. 2006. Natural deduction calculus for computation tree logic. in: IEEE John Vincent Atanasoff 2006 International Symposium on Modern Computing (JVA'06) Los Alamitos, USA IEEE . pp. 175-183

Natural deduction calculus for linear-time temporal logic

Bolotov, A., Basukoski, A., Grigoriev, O. and Shangin, V. 2006. Natural deduction calculus for linear-time temporal logic. in: Fisher, M., van der Hoek, W., Konev, B. and Lisitsa, A. (ed.) Logics in artificial intelligence: 10th European conference, JELIA 2006: Liverpool, UK September 13-15 2006: proceedings Berlin, Germany Springer.

Specification and verification of reconfiguration protocols in grid component systems

Basso, A., Bolotov, A., Basukoski, A., Getov, Vladimir, Henrio, L. and Urbanski, M. 2006. Specification and verification of reconfiguration protocols in grid component systems. in: Proceedings of the 3rd IEEE International Conference on Intelligent Systems (IS-2006) Los Alamitos, USA IEEE . pp. 450-455

Alternating automata and temporal logic normal forms

Dixon, C., Bolotov, A. and Fisher, M. 2005. Alternating automata and temporal logic normal forms. *Annals of Pure and Applied Logic.* 135 (1-3), pp. 263-285. doi:10.1016/j.apal.2005.03.002

Normative agents: formal analysis and applications

Bolotov, A. and Svigkos, I. 2005. Normative agents: formal analysis and applications. in: Proceedings of the International Conference Business at the Heart of Central Asia: Critical Issues of Competition and Competitiveness Westminster International University in Tashkent.

Proof-searching algorithm in first order classical natural deduction calculus

Bolotov, A., Bocharov, V., Gorchakov, A. and Shangin, V. 2005. Proof-searching algorithm in first order classical natural deduction calculus. in: Hajek, P., Valdes-Villanueva, L. and Westerstahl, D. (ed.) Logic, methodology and philosophy of science: proceedings of the twelfth international congress King's College Publications.

Automated first order natural deduction

Bolotov, A., Bocharov, V., Gorchakov, A. and Shangin, V. 2005. Automated first order natural deduction. in: Prasad, B. (ed.) Proceedings of the 2nd Indian International Conference on Artificial Intelligence, Pune, India, December 20-22, 2005. IICAI 2005 ISCAI. pp. 1292-1311

Search strategies for resolution in CTL-type logics: extension and complexity

Basukoski, A. and Bolotov, A. 2005. Search strategies for resolution in CTL-type logics: extension and complexity. in: 12th International Symposium on Temporal Representation and Reasoning, 2005: TIME 2005 Los Alamitos, USA IEEE . pp. 195-197

Let the computer prove it

Bolotov, A., Bocharov, V., Gorchakov, A., Makarov, V. and Shangin, V. 2004. *Let the computer prove it.* Moscow, Russia Nauka.

A clausal resolution method for branching-time logic ECTL+

Bolotov, A. and Basukoski, A. 2004. A clausal resolution method for branching-time logic ECTL+. in: Combi, C. (ed.) 11th International Symposium on Temporal Representation and Reasoning: (TIME 2004), Tatihou, Normandie, France, 1-3 July 2004 IEEE . pp. 140-147

The scientist and his time

Bolotov, A. and Zaitzev, D. 2003. The scientist and his time. *Logical Studies.* 10, pp. 1-9.

A clausal resolution for extended computation tree logic ECTL

Bolotov, A. 2003. A clausal resolution for extended computation tree logic ECTL. in: Reynolds, M. and Sattar, A. (ed.) Proceedings of the Combined Tenth International Symposium on Temporal Representation and Reasoning and the Fourth International Conference on Temporal Logic: TIME-ICTL 2003 Cairns, Queensland, Australia, 8-10 July 2003 USA IEEE . pp. 107-117

On the relationship between w-automata and temporal logic normal forms

Bolotov, A., Fisher, M. and Dixon, C. 2002. On the relationship between w-automata and temporal logic normal forms. *Journal of Logic and Computation.* 12 (4), pp. 561-581. doi:10.1093/logcom/12.4.561

Clausal resolution in a logic of rational agency

Dixon, C., Fisher, M. and Bolotov, A. 2002. Clausal resolution in a logic of rational agency. *Artificial Intelligence: an international journal.* 139 (1), pp. 47-89. doi:10.1016/S0004-3702(02)00196-0

**Permalink - **https://westminsterresearch.westminster.ac.uk/item/qy9vw/branching-time-logic-ectl-and-its-tree-style-one-pass-tableau-extending-fairness-expressibility-of-ectl

Accepted author manuscript

Under embargo until 13 Feb 20218 total views

0 total downloads

0 views this month

0 downloads this month