Log in

Relevant bibliographies by topics / Two-variable first-order logic with counting quantifiers

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers

Academic literature on the topic 'Two-variable first-order logic with counting quantifiers'

Author: Grafiati

Published: 4 June 2021

Last updated: 14 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Two-variable first-order logic with counting quantifiers.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Two-variable first-order logic with counting quantifiers"

1

Kuzelka, Ondrej. "Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers." Journal of Artificial Intelligence Research 70 (March 29, 2021): 1281–307. http://dx.doi.org/10.1613/jair.1.12320.

Full text

Abstract:

It is known due to the work of Van den Broeck, Meert and Darwiche that weighted first-order model counting (WFOMC) in the two-variable fragment of first-order logic can be solved in time polynomial in the number of domain elements. In this paper we extend this result to the two-variable fragment with counting quantifiers.

APA, Harvard, Vancouver, ISO, and other styles

2

Hella, Lauri, Leonid Libkin, and Juha Nurmonen. "Notions of locality and their logical characterizations over finite models." Journal of Symbolic Logic 64, no. 4 (1999): 1751–73. http://dx.doi.org/10.2307/2586810.

Full text

Abstract:

AbstractMany known tools for proving expressibility bounds for first-ordér logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond t

APA, Harvard, Vancouver, ISO, and other styles

3

Grohe, Martin. "Finite Variable Logics in Descriptive Complexity Theory." Bulletin of Symbolic Logic 4, no. 4 (1998): 345–98. http://dx.doi.org/10.2307/420954.

Full text

Abstract:

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k (free or bound) variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers.Finite variable logics have mostly been studied

APA, Harvard, Vancouver, ISO, and other styles

4

Pacholski, Leszek, WiesL aw Szwast, and Lidia Tendera. "Complexity Results for First-Order Two-Variable Logic with Counting." SIAM Journal on Computing 29, no. 4 (2000): 1083–117. http://dx.doi.org/10.1137/s0097539797323005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Szwast, Wiesław, and Lidia Tendera. "On the satisfiability problem for fragments of two-variable logic with one transitive relation." Journal of Logic and Computation 29, no. 6 (2019): 881–911. http://dx.doi.org/10.1093/logcom/exz012.

Full text

Abstract:

Abstract We study the satisfiability problem for two-variable first-order logic over structures with one transitive relation. We show that the problem is decidable in 2-NExpTime for the fragment consisting of formulas where existential quantifiers are guarded by transitive atoms. As this fragment enjoys neither the finite model property nor the tree model property, to show decidability we introduce a novel model construction technique based on the infinite Ramsey theorem. We also point out why the technique is not sufficient to obtain decidability for the full two-variable logic with one trans

APA, Harvard, Vancouver, ISO, and other styles

6

Niemistö, Hannu. "Zero-one law and definability of linear order." Journal of Symbolic Logic 74, no. 1 (2009): 105–23. http://dx.doi.org/10.2178/jsl/1231082304.

Full text

Abstract:

§1. Introduction. A logic ℒ has a limit law, if the asymptotic probability of every query definable in ℒ converges. It has a 0–1-law if the probability converges to 0 or 1. The 0–1-law for first-order logic on relational vocabularies was independently found by Glebski et al. [6] and Fagin [5]. Later it has been shown for many other logics, for instance for fragments of second order logic [12], for finite variable logic [13] and for FO extended with the rigidity quantifier [3]. Lynch [14] has shown a limit law for first-order logic on vocabularies with unary functions.We say that two formulas o

APA, Harvard, Vancouver, ISO, and other styles

7

BELLODI, ELENA, EVELINA LAMMA, FABRIZIO RIGUZZI, VITOR SANTOS COSTA, and RICCARDO ZESE. "Lifted Variable Elimination for Probabilistic Logic Programming." Theory and Practice of Logic Programming 14, no. 4-5 (2014): 681–95. http://dx.doi.org/10.1017/s1471068414000283.

Full text

Abstract:

AbstractLifted inference has been proposed for various probabilistic logical frameworks in order to compute the probability of queries in a time that depends on the size of the domains of the random variables rather than the number of instances. Even if various authors have underlined its importance for probabilistic logic programming (PLP), lifted inference has been applied up to now only to relational languages outside of logic programming. In this paper we adapt Generalized Counting First Order Variable Elimination (GC-FOVE) to the problem of computing the probability of queries to probabil

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Two-variable first-order logic with counting quantifiers"

1

Kourtis, Georgios. "Path-functional dependencies and the two-variable guarded fragment with counting." Thesis, University of Manchester, 2017. https://www.research.manchester.ac.uk/portal/en/theses/pathfunctional-dependencies-and-the-twovariable-guarded-fragment-with-counting(eac338a1-4fd4-49b6-91ee-8ea2ffaee9d2).html.

Full text

Abstract:

We examine how logical reasoning in the two-variable guarded fragment with counting quantifiers can be integrated with databases in the presence of certain integrity constraints, called path-functional dependencies. In more detail, we establish that the problems of satisfiability and finite satisfiability for the two-variable guarded fragment with counting quantifiers, a database, and binary path-functional dependencies are EXPTIME-complete; we also establish that the data complexity of these problems is NP-complete. We establish that query answering for the above fragment (with a database and

APA, Harvard, Vancouver, ISO, and other styles

2

Gu, Yilan. "Advanced Reasoning about Dynamical Systems." Thesis, 2010. http://hdl.handle.net/1807/26274.

Full text

Abstract:

In this thesis, we study advanced reasoning about dynamical systems in a logical framework -- the situation calculus. In particular, we consider promoting the efficiency of reasoning about action in the situation calculus from three different aspects. First, we propose a modified situation calculus based on the two-variable predicate logic with counting quantifiers. We show that solving the projection and executability problems via regression in such language are decidable. We prove that generally these two problems are co-NExpTime-complete in the modified language. We also consider restric

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Two-variable first-order logic with counting quantifiers"

1

Button, Tim, and Sean Walsh. Logics and languages. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780198790396.003.0001.

Full text

Abstract:

This chapter introduces the concepts of signature and structure, and describes the semantics for first- and second-order logic. We outline three different but extensionally equivalent treatments of quantifiers and variables (the Tarskian approach, the Robinsonian approach, and a hybrid approach) and discuss their philosophical merits concerning compositionality, and Fine’s antinomy of the variable. We also outline two extensionally distinct semantics for second-order logic (Henkin, full). The appendix to the chapter presents the formal definitions of some theories of arithmetic and set theory

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Two-variable first-order logic with counting quantifiers"

1

Lodaya, Kamal, and A. V. Sreejith. "Two-Variable First Order Logic with Counting Quantifiers: Complexity Results." In Developments in Language Theory. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-62809-7_19.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Two-variable first-order logic with counting quantifiers"

1

Bednarczyk, Bartosz, and Sebastian Rudolph. "Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/212.

Full text

Abstract:

Among the most expressive knowledge representation formalisms are the description logics of the Z family. For well-behaved fragments of ZOIQ, entailment of positive two-way regular path queries is well known to be 2EXPTIME-complete under the proviso of unary encoding of numbers in cardinality constraints. We show that this assumption can be dropped without an increase in complexity and EXPTIME-completeness can be achieved when bounding the number of query atoms, using a novel reduction from query entailment to knowledge base satisfiability. These findings allow to strengthen other results rega

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!