|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Logics
On safety of unary and non-unary IFP-operators
S. M. Dudakov Tver State University,
33 Zhelyabova str., Tver 170100, Russia
Abstract:
In this paper, we investigate the safety of
unary inflationary fixed point operators (IFP-operators).
The safety is a computability in finitely many steps.
IFP-operators exactly correspond to recursive SQL-queries
hence this problem has a value for database theory.
The problem appears from the fact that
if recursive queries contain universe functions and relations, then its execution can fall into an infinite loop.
Moreover, universal computational devices
(Turing machines et al.) can be modelled
by such queries.
Hence the problem of the finite computability for such queries
is undecidable.
In our previous works we established some properties
of a universe which imply the finite computability
of all IFP-operators in the universe.
Here, we investigate a connection
between an arity of IFP-operators and their safety.
We prove that some results for general IFP-operators don't hold
for unary ones.
We construct a universe where all unary unnesed IFP-operators are safe.
But in this universe there exist unsafe nested unary IFP-operators
and unsafe unnested binary IFP-operators.
This differs from general IFP-operators because in general case
the safety of all unnesed IFP-operators implies the safety of all IFP-operators.
Also there exist elementary equivalent universes where
some unary unnesed IFP-operators become unsafe.
For general IFP-operators it is also impossible.
Keywords:
inflationary fixed point, arity, safety.
Received: 10.09.2018
Citation:
S. M. Dudakov, “On safety of unary and non-unary IFP-operators”, Model. Anal. Inform. Sist., 25:5 (2018), 525–533
Linking options:
https://www.mathnet.ru/eng/mais646 https://www.mathnet.ru/eng/mais/v25/i5/p525
|
Statistics & downloads: |
Abstract page: | 192 | Full-text PDF : | 51 | References: | 31 |
|