The complexity of McNaughton functions of one variable
type: Item
instance of: scholarly article
title: The complexity of McNaughton functions of one variable
zbMATH Open document ID: 0911.03004
author: Stefano Aguzzoli
published in: Advances in Applied Mathematics
publication date: 1999-05-04T00:00:00Z
review text: In a paper jointly written by the present reviewer with \textit{N. Olivetti}, entitled ``Resolution and model building in the infinite-valued calculus of Łukasiewicz'' [Theor. Comput. Sci. 200, 335-366 (1998)], appropriate generalizations of the classical notions of literal, clause, and resolution are introduced, in view of applications to infinite-valued automated deduction. Literals are defined as nonconstant monotone univariate McNaughton functions, and it is asked whether positive literals coincide with functions represented by formulas in one variable, only using Łukasiewicz conjunction and disjunction. In the paper under review a positive answer is given to this problem, by means of a deep analysis of the subtleties of McNaughton functions. Among others, the author defines a procedure to build univariate McNaughton functions much more quickly than is done by \textit{A. Rose} and \textit{J. B. Rosser} in their paper ``Fragments of many-valued statement calculi'' [Trans. Am. Math. Soc. 87, 1-53 (1958; Zbl 0085.24303)].
Mathematics Subject Classification ID: 03B35
Mathematics Subject Classification ID: 03B50
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 1221610
zbMATH Keywords: piecewise linear
zbMATH Keywords: Lukasiewicz calculus
zbMATH Keywords: McNaughton functions
reviewed by: Daniele Mundici
MaRDI profile type: Publication
full work available at URL: aama.1998.0581
OpenAlex ID: W2043639987
cites work: An algorithmic desingularization of 3-dimensional toric varieties
cites work: A theorem about infinite-valued sentential logic
cites work: Satisfiability in many-valued sentential logic is NP-complete
cites work: Q4202949
cites work: A constructive proof of McNaughton's theorem in infinite-valued logic
cites work: Q3837739
cites work: Resolution and model building in the infinite-valued calculus of Łukasiewicz
cites work: A geometric proof of the completeness of the Łukasiewicz calculus
cites work: Fragments of Many-Valued Statement Calculi
DOI: 10.1006/AAMA.1998.0581
description: scientific article; zbMATH DE number 1221610