%0 Conference Paper %1 degiacomo2014reasoning %A De Giacomo, Giuseppe %A De Masellis, Riccardo %A Marco, Montali %B Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence %D 2014 %I AAAI Press %K LTL optique-project %P 1027-1033 %T Reasoning on LTL on Finite Traces: Insensitivity to Infiniteness. %X In this paper we study when an LTL formula on finite traces (LTLf formula) is insensitive to infiniteness, that is,it can be correctly handled as a formula on infinite traces under the assumption that at a certain point the infinite trace starts repeating an end event forever, trivializing all other propositions to false. This intuition has been put forward and (wrongly) assumed to hold in general in the literature. We define a necessary and sufficient condition to characterize whether an LTLf formula is insensitive to infiniteness, which can be automatically checked by any LTL reasoner. Then, we show that typical LTLf specification patterns used in process and service modeling in CS, as well as trajectory constraints in Planning and transition-based LTLf specifications of action domains in KR, are indeed very often insensitive to infiniteness. This may help to explain why the assumption of interpreting LTL on finite and on infinite traces has been (wrongly) blurred. Possibly be- cause of this blurring, virtually all literature detours to Buchi automata for constructing the NFA that accepts the traces satisfying an LTLf formula. As a further contribution, we give a simple direct algorithm for computing such NFA.

@inproceedings{degiacomo2014reasoning, abstract = {In this paper we study when an LTL formula on finite traces (LTLf formula) is insensitive to infiniteness, that is,it can be correctly handled as a formula on infinite traces under the assumption that at a certain point the infinite trace starts repeating an end event forever, trivializing all other propositions to false. This intuition has been put forward and (wrongly) assumed to hold in general in the literature. We define a necessary and sufficient condition to characterize whether an LTLf formula is insensitive to infiniteness, which can be automatically checked by any LTL reasoner. Then, we show that typical LTLf specification patterns used in process and service modeling in CS, as well as trajectory constraints in Planning and transition-based LTLf specifications of action domains in KR, are indeed very often insensitive to infiniteness. This may help to explain why the assumption of interpreting LTL on finite and on infinite traces has been (wrongly) blurred. Possibly be- cause of this blurring, virtually all literature detours to Buchi automata for constructing the NFA that accepts the traces satisfying an LTLf formula. As a further contribution, we give a simple direct algorithm for computing such NFA.}, added-at = {2014-10-16T10:30:12.000+0200}, audience = {academic}, author = {De Giacomo, Giuseppe and De Masellis, Riccardo and Marco, Montali}, biburl = {https://www.bibsonomy.org/bibtex/23110caac7cbb0b720a90fdc52dab0c29/savo.fabio}, booktitle = {Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence}, interhash = {b5f8415a7a92dfa47c1b5b53f0459460}, intrahash = {3110caac7cbb0b720a90fdc52dab0c29}, keywords = {LTL optique-project}, openaccess = {Yes}, pages = {1027-1033}, partneroptique = {UNIROMA1}, publisher = {AAAI Press}, timestamp = {2016-12-01T19:22:01.000+0100}, title = {Reasoning on LTL on Finite Traces: Insensitivity to Infiniteness.}, wpoptique = {WP4}, year = 2014, yearoptique = {Y2} }