Log in

Relevant bibliographies by topics / Second-order existential logic

Contents

Journal articles
Dissertations / Theses
Books
Book chapters

Academic literature on the topic 'Second-order existential logic'

Author: Grafiati

Published: 4 June 2021

Last updated: 15 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 'Second-order existential logic.'

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 "Second-order existential logic"

1

BESSON, CORINE. "EXTERNALISM, INTERNALISM, AND LOGICAL TRUTH." Review of Symbolic Logic 2, no. 1 (March 2009): 1–29. http://dx.doi.org/10.1017/s1755020309090091.

Full text

Abstract:

The aim of this paper is to show what sorts of logics are required by externalist and internalist accounts of the meanings of natural kind nouns. These logics give us a new perspective from which to evaluate the respective positions in the externalist--internalist debate about the meanings of such nouns. The two main claims of the paper are the following: first, that adequate logics for internalism and externalism about natural kind nouns are second-order logics; second, that an internalist second-order logic is a free logic—a second order logic free of existential commitments for natural kind nouns, while an externalist second-order logic is not free of existential commitments for natural kind nouns—it is existentially committed.

APA, Harvard, Vancouver, ISO, and other styles

2

Eiter, Thomas, Georg Gottlob, and Yuri Gurevich. "Existential second-order logic over strings." Journal of the ACM 47, no. 1 (January 2000): 77–131. http://dx.doi.org/10.1145/331605.331609.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Gottlob, Georg, Phokion G. Kolaitis, and Thomas Schwentick. "Existential second-order logic over graphs." Journal of the ACM 51, no. 2 (March 2004): 312–62. http://dx.doi.org/10.1145/972639.972646.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Rosen, Eric. "An existential fragment of second order logic." Archive for Mathematical Logic 38, no. 4-5 (May 1, 1999): 217–34. http://dx.doi.org/10.1007/s001530050126.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Hale, Bob. "Second-order logic: properties, semantics, and existential commitments." Synthese 196, no. 7 (May 30, 2015): 2643–69. http://dx.doi.org/10.1007/s11229-015-0764-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Pacholski, Leszek, and WiesŁaw Szwast. "Asymptotic probabilities of existential second-order Gödel sentences." Journal of Symbolic Logic 56, no. 2 (June 1991): 427–38. http://dx.doi.org/10.2307/2274691.

Full text

Abstract:

In [9] and [10] P. Kolaitis and M. Vardi proved that the 0-1 law holds for the second-order existential sentences whose first-order parts are formulas of Bernays-Schonfinkel or Ackermann prefix classes. They also provided several examples of second-order formulas for which the 0-1 law does not hold, and noticed that the classification of second-order sentences for which the 0-1 law holds resembles the classification of decidable cases of first-order prenex sentences. The only cases they have not settled are the cases of Gödel classes with and without equality.In this paper we confirm the conjecture of Kolaitis and Vardi that the 0-1 law does not hold for the existential second-order sentences whose first-order part is in Gödel prenex form with equality. The proof we give is based on a modification of the example employed by W. Goldfarb [5] in his proof that, contrary to the Gödel claim [6], the class of Gödel prenex formulas with equality is undecidable.

APA, Harvard, Vancouver, ISO, and other styles

7

Hella, Lauri, and Antti Kuusisto. "Existential second-order logic and modal logic with quantified accessibility relations." Information and Computation 247 (April 2016): 217–34. http://dx.doi.org/10.1016/j.ic.2016.01.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Holroyd, Alexander E., Avi Levy, Moumanti Podder, and Joel Spencer. "Existential monadic second order logic on random rooted trees." Discrete Mathematics 342, no. 1 (January 2019): 152–67. http://dx.doi.org/10.1016/j.disc.2018.09.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Zhukovskii, M. E. "Logical laws for short existential monadic second-order sentences about graphs." Journal of Mathematical Logic 20, no. 02 (December 12, 2019): 2050007. http://dx.doi.org/10.1142/s0219061320500075.

Full text

Abstract:

In 2001, Le Bars proved that there exists an existential monadic second-order (EMSO) sentence such that the probability that it is true on [Formula: see text] does not converge and conjectured that, for EMSO sentences with two first-order variables, the zero–one law holds. In this paper, we prove that the conjecture fails for [Formula: see text], and give new examples of sentences with fewer variables without convergence (even for [Formula: see text]).

APA, Harvard, Vancouver, ISO, and other styles

10

Vedø, Anne. "Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences." Journal of Symbolic Logic 62, no. 1 (March 1997): 304–19. http://dx.doi.org/10.2307/2275743.

Full text

Abstract:

AbstractWe show that the 0-1 law does not hold for the class(∀∃∀ without = ) by finding a sentence in this class which almost surely expresses parity. We also show that every recursive real in the unit interval is the asymptotic probability of a sentence in this class. This expands a result by Lidia Tendera, who in 1994 proved that everyrationalnumber in the unit interval is the asymptotic probability of a sentence in the class∀∃∀withequality.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Second-order existential logic"

1

Hoelzel, Matthias [Verfasser], Erich [Akademischer Betreuer] Grädel, and Lauri [Akademischer Betreuer] Hella. "Fragments of existential second-order logic and logics with team semantics / Matthias Hoelzel ; Erich Grädel, Lauri Hella." Aachen : Universitätsbibliothek der RWTH Aachen, 2019. http://d-nb.info/1217503811/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Nijjar, Paul. "An Attempt to Automate NP-Hardness Reductions via SO∃ Logic." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1162.

Full text

Abstract:

We explore the possibility of automating NP-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (SO∃) logic as representation language for decision problems. Building upon the theoretical framework of J. Antonio Medina, we explore the possibility of implementing seven syntactic operators. Each operator transforms SO∃ sentences in a way that preserves NP-completeness. We subsequently propose a program which implements these operators. We discuss a number of theoretical and practical barriers to this task. We prove that determining whether two SO∃ sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary SO∃ sentence represents an NP-complete problem is undecidable.

APA, Harvard, Vancouver, ISO, and other styles

3

Ågren, Magnus. "Set Constraints for Local Search." Doctoral thesis, Uppsala universitet, Avdelningen för datalogi, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8373.

Full text

Abstract:

Combinatorial problems are ubiquitous in our society and solving such problems efficiently is often crucial. One technique for solving combinatorial problems is constraint-based local search. Its compositional nature together with its efficiency on large problem instances have made this technique particularly attractive. In this thesis we contribute to simplifying the solving of combinatorial problems using constraint-based local search. To provide higher-level modelling options, we introduce set variables and set constraints in local search by extending relevant local search concepts. We also propose a general scheme to follow in order to define what we call natural and balanced constraint measures, and accordingly define such measures for over a dozen set constraints. However, defining such measures for a new constraint is time-consuming and error-prone. To relieve the user from this, we provide generic measures for any set constraint modelled in monadic existential second-order logic. We also theoretically relate these measures to our proposed general scheme, and discuss implementation issues such as incremental algorithms and their worst-case complexities. To enable higher-level search algorithms, we introduce constraint-directed neighbourhoods in local search by proposing new constraint primitives for representing such neighbourhoods. Based on a constraint, possibly modelled in monadic existential second-order logic, these primitives return neighbourhoods with moves that are known in advance to achieve a decrease (or preservation, or increase) of the constraint measures, without the need to iterate over any other moves. We also present a framework for constraint-based local search where one can model and solve combinatorial problems with set variables and set constraints, use any set constraint modelled in monadic existential second-order logic, as well as use constraint-directed neighbourhoods. Experimental results on three real-life problems show the usefulness in practice of our theoretical results: our running times are comparable to the current state-of-the-art approaches to solving the considered problems.

APA, Harvard, Vancouver, ISO, and other styles

4

Grente, Theo. "Caractérisation et programmation en théorie des langages et en logique des classes de complexité efficace des automates cellulaires." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMC214.

Full text

Abstract:

Les automates cellulaires constituent le modèle de calcul parallèle et local par excellence.Comme pour tout modèle du parallélisme, leur programmation est réputée difficile. La puissance de calcul des automates cellulaires, modèle le plus simple du parallélisme, est attestée par le fait que nombre de problèmes significatifs sont calculés en temps minimal, appelé temps-réel, surautomate cellulaire.Principal résultat de cette thèse, on démontre des liens exacts (des équivalences) entre d’un côté la complexité descriptive, essentiellement la définissabilité en logique du second ordre existentiel sur des formules de Horn, de l’autre les classes de complexité en temps-réel des automates cellulaires.Au-delà de cette caractérisation en logique de la complexité en temps minimal, la thèse établit une méthode de programmation parallèle. Cette méthode consiste dans un premier temps à programmer dans nos logiques de Horn l’induction résolvant un problème, puis dans un secondtemps, à appliquer un processus automatique aboutissant au programme de l’automate cellulaire résolvant le problème. Pour justifier l’intérêt de la méthode, la thèse présente un ensemble de programmes logiques pour une variété représentative de problèmes classiques connus pour êtrecalculables en temps-réel sur automates cellulaires.Par ailleurs, toujours en passant par nos logiques, on prouve divers résultats liant le temps-réel des automates cellulaires et les grammaires formelles. Typiquement, tout langage généré par une grammaire algébrique et, plus généralement, une grammaire conjonctive d’Okhotin, est reconnu en temps-réel sur un automate cellulaire de dimension 2
Cellular automata constitute the model of parallel and local computation by excellence.As for any model of parallelism, their programming is known to be difficult. The computingpower of cellular automata, the simplest model of parallelism, is attested by the fact that manysignificant problems are computed in minimal time, called real-time, on cellular automata.The main result of this thesis is the demonstration of exact links (equivalences) between, on onehand, the descriptive complexity, essentially the definability in existential second order logic on Horn formulas, and, on the other hand, the real-time complexity classes of cellular automata.Beyond this characterization in logic of the complexity in minimal time, the thesis establishes a method of parallel programming. This method consists first of all in programming in our Horn ogics the induction solving a problem, then in a second step, in applying an automatic process leading to the program of the cellular automaton solving the problem. To justify the interest of the method, the thesis presents a set of logic programs for a representative variety of classical problems known to be computable in real-time on cellular automata.In addition, we prove various results linking the real time of cellular automata and formal grammars. Typically, any language generated by an algebraic grammar and, more generally, an Okhotin conjunctive grammar, is recognized in real-time on a 2-dimensional cellular automaton

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Second-order existential logic"

1

Heck, Richard Kimberly. Logicism, Ontology, and the Epistemology of Second-Order Logic. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780198792161.003.0008.

Full text

Abstract:

In two recent papers, Bob Hale has attempted to free second-order logic of the “staggering existential assumptions” with which Quine famously attempted to saddle it. This chapter argues, first, that the ontological issue is at best secondary: the crucial issue about second-order logic, at least for a neo-logicist, is epistemological. It is then argued that neither Crispin Wright’s attempt to characterize a ‘neutralist’ conception of quantification that is wholly independent of existential commitment, nor Hale’s attempt to characterize the second-order domain in terms of definability, can serve a neo-logicist’s purposes. The problem, in both cases, is similar: neither Wright nor Hale is sufficiently sensitive to the demands that impredicativity imposes. Finally, the chapter defends the author’s own earlier attempt to finesse this issue, in “A Logic for Frege’s Theorem,” from Hale’s criticisms.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Second-order existential logic"

1

Schwentick, Thomas. "Padding and the expressive power of existential second-order logics." In Computer Science Logic, 461–77. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0028031.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Blass, Andreas. "Existential Fixed-Point Logic as a Fragment of Second-Order Logic." In Fields of Logic and Computation II, 52–68. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-23534-9_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Bodirsky, Manuel, Simon Knäuer, and Florian Starke. "ASNP: A Tame Fragment of Existential Second-Order Logic." In Lecture Notes in Computer Science, 149–62. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-51466-2_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Ågren, Magnus, Pierre Flener, and Justin Pearson. "Incremental Algorithms for Local Search from Existential Second-Order Logic." In Principles and Practice of Constraint Programming - CP 2005, 47–61. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11564751_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kolaitis, Phokion G., and Moshe Y. Vardi. "0–1 Laws for Fragments of Existential Second-Order Logic: A Survey." In Lecture Notes in Computer Science, 84–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44612-5_6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Matz, Oliver. "One quantifier will do in existential monadic second-order logic over pictures." In Mathematical Foundations of Computer Science 1998, 751–59. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0055826.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Hannula, Miika, and Jonni Virtema. "Tractability Frontiers in Probabilistic Team Semantics and Existential Second-Order Logic over the Reals." In Logics in Artificial Intelligence, 262–78. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-75775-5_18.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Hale, Bob. "Second-order Logic: Properties, Semantics, and Existential Commitments." In Essence and Existence, edited by Jessica Leech and Kit Fine, 187–212. Oxford University Press, 2020. http://dx.doi.org/10.1093/oso/9780198854296.003.0012.

Full text

Abstract:

Quine’s charge against second-order logic is that it carries massive existential commitments. This chapter argues that if we interpret second-order variables as ranging over properties construed in accordance with an abundant or deflationary conception, Quine’s charge can be resisted. This need not preclude the use of model-theoretic semantics for second-order languages; but it precludes the standard semantics, along with the more general Henkin semantics, of which it is a special case. To that extent, the approach of this chapter has revisionary implications; it is, however, compatible with the different special case in which second-order variables are taken to range over definable subsets of the first-order domain, and with respect to such a semantics, important metalogical results obtainable under the standard semantics may still be obtained. Finally, the chapter discusses the relations between second-order logic, interpreted as recommended, and a strong version of schematic ancestral logic promoted in recent work by Richard Kimberly Heck.

APA, Harvard, Vancouver, ISO, and other styles

9

Yourgrau, Palle. "The Predicate of Existence." In Death and Nonexistence, 14–37. Oxford University Press, 2019. http://dx.doi.org/10.1093/oso/9780190247478.003.0002.

Full text

Abstract:

Kant famously declared that existence is not a (real) predicate. This famous dictum has been seen as echoed in the doctrine of the founders of modern logic, Gottlob Frege and Bertrand Russell, that existence isn’t a first-order property possessed by individuals, but rather a second-order property expressed by the existential quantifier. Russell in 1905 combined this doctrine with his new theory of descriptions and declared the paradox of nonexistence to be resolved without resorting to his earlier distinction between existence and being. In recent years, however, logicians and philosophers like Saul Kripke, David Kaplan, and Nathan Salmon have argued that there is no defensible reason to deny that existence is a property of individuals. Kant’s dictum has also been re-evaluated, the result being that the paradox of nonexistence has not, after all, disappeared. Yet it’s not clear how exactly Kripke et al. propose to resolve the paradox.

APA, Harvard, Vancouver, ISO, and other styles

10

Phillips, John W. P. "Notes from the Underground: Microwaves, Backbones, Party Lines and the Post Office Tower." In Cold War Legacies. Edinburgh University Press, 2016. http://dx.doi.org/10.3366/edinburgh/9781474409483.003.0012.

Full text

Abstract:

This chapter links the essential parasitism of cold war systems to some general trends of 20^th century telecommunications (economically motivated service-oriented multi-media). Certain (existential) fictions of the second half of the century explore and instantiate the peculiar logic of the parasite. The chapter draws out the implications of an ethics grounded in the attempt to deal with this logic and questions where such attempts, and the desires that drive them, might lead. These ethical concerns are connected via technological analysis to the 1956 plan for a radio link (known as Backbone) running north and south through the UK, avoiding large towns and meant to provide a safe route for communications vital to the prosecution of a war. The conjunction of existentialist fiction with the cold war technology ties together a triad of puzzles of the era: communication, existence and the problem of other minds. But the problems have since shifted—the rational subject now comes into being belatedly as an interrupter, a parasite, displacing or replacing the previous parasite. The parasitical arrangement does not follow the formal order of subject and object but occurs intersubjectively, producing its subjects in the process and figuring a fundamental alteration in social relations.

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!