Готові списки джерел за темами / Quantifier arity

Добірка наукової літератури з теми "Quantifier arity"

Автор: Grafiati

Опубліковано: 4 червня 2021

Оновлено: 19 лютого 2022

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Зміст

Статті в журналах

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Quantifier arity".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "Quantifier arity"

Joomwong, Jintana, and Dara Phusanga. "Deterministic and non-deterministic hypersubstitutions for algebraic systems." Asian-European Journal of Mathematics 09, no. 02 (April 15, 2016): 1650047. http://dx.doi.org/10.1142/s1793557116500479.

Повний текст джерела

Анотація:

Hypersubstitutions for algebraic systems are mappings which send operation symbols to terms and relational symbols to formulas preserving arities (see [D. Phusanga, Derived Algebraic Systems, Ph.D. thesis, Potsdam (2013)]). In the non-deterministic case, i.e. if one operation symbol is sent to several terms of the same arity and also one relational symbol is sent to several quantifier free formulas of the same arity, we can consider a mapping from the set of operation symbols into the power set of the set of all terms and from the set of relational symbols into the power set of the set of all quantifier free formulas of the considered type. These mappings are called non-deterministic hypersubstitutions for algebraic systems. We consider sets of algebraic systems which are invariant under non-deterministic hypersubstitutions and apply the result to [Formula: see text]-[Formula: see text]-solid classes of algebraic systems. In this paper, we consider an extension of non-deterministic hypersubstitutions which is based on deterministic ones.

Стилі APA, Harvard, Vancouver, ISO та ін.

Pikhurko, Oleg, and Oleg Verbitsky. "Descriptive complexity of finite structures: Saving the quantifier rank." Journal of Symbolic Logic 70, no. 2 (June 2005): 419–50. http://dx.doi.org/10.2178/jsl/1120224721.

Повний текст джерела

Анотація:

AbstractWe say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M′ over the same vocabulary if Φ is true on M but false on M′. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M′. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M′.We prove that every n-element structure M is identifiable by a formula with quantifier rank less than and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification.The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than quantifiers suffice to identify M and. as long as we keep the number of universal quantifiers bounded by a constant, at total quantifiers are necessary.

Стилі APA, Harvard, Vancouver, ISO та ін.

Grädel, Erich. "On the Restraining Power of Guards." Journal of Symbolic Logic 64, no. 4 (December 1999): 1719–42. http://dx.doi.org/10.2307/2586808.

Повний текст джерела

Анотація:

AbstractGuarded fragments of first-order logic were recently introduced by Andréka, van Benthem and Németi; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all other known decidable fragments of first-order logic.Here, we investigate the computational complexity of these fragments. We prove that the satisfiability problems for the guarded fragment (GF) and the loosely guarded fragment (LGF) of first-order logic are complete for deterministic double exponential time. For the subfragments that have only a bounded number of variables or only relation symbols of bounded arity, satisfiability is Exptime-complete. We further establish a tree model property for both the guarded fragment and the loosely guarded fragment, and give a proof of the finite model property of the guarded fragment.It is also shown that some natural, modest extensions of the guarded fragments are undecidable.

Стилі APA, Harvard, Vancouver, ISO та ін.

Immerman, Neil, Jonathan F. Buss, and David A. Mix Barrington. "Number of variables is equivalent to space." Journal of Symbolic Logic 66, no. 3 (September 2001): 1217–30. http://dx.doi.org/10.2307/2695103.

Повний текст джерела

Анотація:

AbstractWe prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[nk] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = VAR[O[1]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.

Стилі APA, Harvard, Vancouver, ISO та ін.

Zach, Richard. "Decidability of Quantified Propositional Intuitionistic Logic and S4 on Trees of Height and Arity ≤ω". Journal of Philosophical Logic 33, № 2 (квітень 2004): 155–64. http://dx.doi.org/10.1023/b:logi.0000021744.10237.d0.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

LINDELL, STEVEN. "A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES." International Journal of Foundations of Computer Science 19, no. 01 (February 2008): 205–17. http://dx.doi.org/10.1142/s0129054108005632.

Повний текст джерела

Анотація:

We use singulary vocabularies to analyze first-order definability over doubly-linked data structures. Singulary vocabularies contain only monadic predicate and monadic function symbols. A class of mathematical structures in any vocabulary can be elementarily interpreted in a singulary vocabulary, while preserving notions of total size and degree. Doubly-linked data structures are a special case of bounded-degree finite structures in which there are reciprocal connections between elements, corresponding closely with physically feasible models of information storage. They can be associated with logical models involving unary relations and bijective functions in what we call an invertible singulary vocabulary. Over classes of these models, there is a normal form for first-order logic which eliminates all quantification of dependent variables. The paper provides a syntactically based proof using counting quantifiers. It also makes precise the notion of implicit calculability for arbitrary arity first-order formulas. Linear-time evaluation of first-order logic over doubly-linked data structures becomes a direct corollary. Included is a discussion of why these special data structures are appropriate for physically realizable models of information.

Стилі APA, Harvard, Vancouver, ISO та ін.

Areces, Carlos, Miguel Campercholi, Daniel Penazzi, and Pablo Ventura. "The complexity of definability by open first-order formulas." Logic Journal of the IGPL, May 30, 2020. http://dx.doi.org/10.1093/jigpal/jzaa008.

Повний текст джерела

Анотація:

Abstract In this article, we formally define and investigate the computational complexity of the definability problem for open first-order formulas (i.e. quantifier free first-order formulas) with equality. Given a logic $\boldsymbol{\mathcal{L}}$, the $\boldsymbol{\mathcal{L}}$-definability problem for finite structures takes as an input a finite structure $\boldsymbol{A}$ and a target relation $T$ over the domain of $\boldsymbol{A}$ and determines whether there is a formula of $\boldsymbol{\mathcal{L}}$ whose interpretation in $\boldsymbol{A}$ coincides with $T$. We show that the complexity of this problem for open first-order formulas (open definability, for short) is coNP-complete. We also investigate the parametric complexity of the problem and prove that if the size and the arity of the target relation $T$ are taken as parameters, then open definability is $\textrm{coW}[1]$-complete for every vocabulary $\tau $ with at least one, at least binary, relation.

Стилі APA, Harvard, Vancouver, ISO та ін.

Nikitchenko, Mykola, and Valentyn Tymofieiev. "Satisfiability in composition-nominative logics." Open Computer Science 2, no. 3 (January 1, 2012). http://dx.doi.org/10.2478/s13537-012-0027-3.

Повний текст джерела

Анотація:

AbstractComposition-nominative logics are algebra-based logics of partial predicates constructed in a semantic-syntactic style on the methodological basis, which is common with programming. They can be considered as generalizations of traditional logics on classes of partial predicates that do not have fixed arity. In this paper we present and investigate algorithms for solving the satisfiability problem in various classes of composition-nominative logics. We consider the satisfiability problem for logics of the propositional, renominative, and quantifier levels and prove the reduction of the problem to the satisfiability problem for classical logics. The method developed in the paper enables us to leverage existent state-of-the-art satisfiability checking procedures for solving the satisfiability problem in composition-nominative logics, which could be crucial for handling industrial instances coming from domains such as program analysis and verification. The reduction proposed in the paper requires extension of logic language and logic models with an infinite number of unessential variables and with a predicate of equality to a constant.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!