Preservation of expressive completeness in temporal models
type: Item
instance of: scholarly article
title: Preservation of expressive completeness in temporal models
zbMATH Open document ID: 0621.03008
DOI: 10.1016/0890-5401(87)90051-4
author: Amihood Amir
author: Dov Gabbay
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: The paper deals with the problem of expressive completeness of tense logic. Time model is a partially ordered structure \(<T,<,=>\), where T is a nonempty set (of moments of time). A wff of a temporal propositional calculus is built in an obvious manner. The concept of (generalized) truth tables is used. It is a flexible tool for semantic interpretation of temporal connectives. Intuitively, it is a rule of computing the value \(\| \#(A_ 1,...,A_ n)\|_ t^ h\) from values of \(\| A_ i\|^ h_ s\), where {\#} is an n-ary connective, t, s are moments of time, h is an assignment (a function from atoms to subsets of T). The truth table is defined as a predicate logic formula over \(<T,<,=>\). The concept of a table \(\psi_{\#}\) defining a connective {\#} is introduced. The problem (of expressive completeness) is: Is there a finite set C of connectives with which for any given table \(\psi_ A\) a corresponding wff A can be built? Some previous results are presented in the paper: there is no expressive completeness over the general ordered model; expressive completeness was shown over linear models. The authors have investigated some extensions of linear time models preserving the expressive completeness. The concept of a lexicographic product of time models is defined. The main results are: a lexicographic product of expressively complete time models is expressively complete; a constructive proof of this fact enables a description of the set of connectives expressively complete over the lexicographic product. A technique based on the concept of H-dimension (the minimal number of various bound variables needed in a table over \(<T,<,=>)\) is used. The equivalence of a finite H-dimension and expressive completeness holds in the case of m-dimensional connectives (connectives whose interpretation refers to m moments of time). A syntactic separation of variables corresponding to various basic time models is used. The preservation of finite H-dimensions is demonstrated using such…
Mathematics Subject Classification ID: 03B45
zbMATH DE Number: 4006234
zbMATH Keywords: expressive completeness
zbMATH Keywords: tense logic
zbMATH Keywords: temporal propositional calculus
zbMATH Keywords: truth table
zbMATH Keywords: lexicographic product of time models
zbMATH Keywords: m-dimensional connectives
reviewed by: Jan Šefránek
MaRDI profile type: Publication
full work available at URL: 0890-5401(87)90051-4
OpenAlex ID: W1983745898
cites work: Q3867808
cites work: Investigations in modal and tense logics with applications to problems in philosophy and linguistics
cites work: Q3674621
cites work: Q5549024
description: scientific article; zbMATH DE number 4006234