Log in

Relevant bibliographies by topics / Automatic theorem proving. Computational complexity

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers

Academic literature on the topic 'Automatic theorem proving. Computational complexity'

Author: Grafiati

Published: 4 June 2021

Last updated: 3 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 'Automatic theorem proving. Computational complexity.'

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 "Automatic theorem proving. Computational complexity"

1

Dordopulo, A. I. "APPLICATION OF PERFORMANCE REDUCTION METHODS FOR MINIMIZATION OF ANALYZED NUMBER OF PARALLEL PROGRAM VARIANTS." Vestnik komp'iuternykh i informatsionnykh tekhnologii, no. 183 (September 2019): 43–49. http://dx.doi.org/10.14489/vkit.2019.09.pp.043-049.

Full text

Abstract:

In this paper, we review and compare the methods of parallel applications’ development based on the automatic program parallelizing for computer systems with shared and distributed memory and on the information graph’s hardware costs and performance reduction for reconfigurable computer systems. The increase in the number of computer system’s units or in the problem’s dimension leads to the significant growth of the automatic parallelization complexity for a procedural program. As a result, the obtainment of parallelizing results in acceptable time using state-of-the-art computer systems is ve

APA, Harvard, Vancouver, ISO, and other styles

2

Urquhart, Alasdair. "The Complexity of Propositional Proofs." Bulletin of Symbolic Logic 1, no. 4 (1995): 425–67. http://dx.doi.org/10.2307/421131.

Full text

Abstract:

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest paper in the subject is a ground-breaking article by Tseit

APA, Harvard, Vancouver, ISO, and other styles

3

Zucker, Jean-Daniel. "A grounded theory of abstraction in artificial intelligence." Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences 358, no. 1435 (2003): 1293–309. http://dx.doi.org/10.1098/rstb.2003.1308.

Full text

Abstract:

In artificial intelligence, abstraction is commonly used to account for the use of various levels of details in a given representation language or the ability to change from one level to another while preserving useful properties. Abstraction has been mainly studied in problem solving, theorem proving, knowledge representation (in particular for spatial and temporal reasoning) and machine learning. In such contexts, abstraction is defined as a mapping between formalisms that reduces the computational complexity of the task at stake. By analysing the notion of abstraction from an information qu

APA, Harvard, Vancouver, ISO, and other styles

4

HUET, GÉRARD. "Special issue on ‘Logical frameworks and metalanguages’." Journal of Functional Programming 13, no. 2 (2003): 257–60. http://dx.doi.org/10.1017/s0956796802004549.

Full text

Abstract:

There is both a great unity and a great diversity in presentations of logic. The diversity is staggering indeed – propositional logic, first-order logic, higher-order logic belong to one classification; linear logic, intuitionistic logic, classical logic, modal and temporal logics belong to another one. Logical deduction may be presented as a Hilbert style of combinators, as a natural deduction system, as sequent calculus, as proof nets of one variety or other, etc. Logic, originally a field of philosophy, turned into algebra with Boole, and more generally into meta-mathematics with Frege and

APA, Harvard, Vancouver, ISO, and other styles

5

Hasan, Osman, and Sofiène Tahar. "Formally Analyzing Expected Time Complexity of Algorithms Using Theorem Proving." Journal of Computer Science and Technology 25, no. 6 (2010): 1305–20. http://dx.doi.org/10.1007/s11390-010-9407-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Hustadt, Ullrich, Ana Ozaki, and Clare Dixon. "Theorem Proving for Pointwise Metric Temporal Logic Over the Naturals via Translations." Journal of Automated Reasoning 64, no. 8 (2020): 1553–610. http://dx.doi.org/10.1007/s10817-020-09541-4.

Full text

Abstract:

Abstract We study translations from metric temporal logic (MTL) over the natural numbers to linear temporal logic (LTL). In particular, we present two approaches for translating from MTL to LTL which preserve the complexity of the satisfiability problem for MTL. In each of these approaches we consider the case where the mapping between states and time points is given by (i) a strict monotonic function and by (ii) a non-strict monotonic function (which allows multiple states to be mapped to the same time point). We use this logic to model examples from robotics, traffic management, and scheduli

APA, Harvard, Vancouver, ISO, and other styles

7

Snyers and Thayse. "Algorithmic State Machine Design and Automatic Theorem Proving: Two Dual Approaches to the Same Activity." IEEE Transactions on Computers C-35, no. 10 (1986): 853–61. http://dx.doi.org/10.1109/tc.1986.1676676.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Su, Wei, Chuan Cai, Paul S. Wang, Hengjie Li, Zhen Huang, and Qiang Huang. "Complexity of Mathematical Expressions and Its Application in Automatic Answer Checking." Symmetry 13, no. 2 (2021): 188. http://dx.doi.org/10.3390/sym13020188.

Full text

Abstract:

The complexity of a mathematical expression is a measure that can be used to compare the expression with other mathematical expressions and judge which one is simpler. In the paper, we analyze three effect factors for the complexity of a mathematical expression: representational length, computational time, and intelligibility. Mainly, the paper introduces a binary-lambda-calculus based calculation method for representational complexity and a rule based calculation method for algebraic computation complexity. In the process of calculating the representation complexity of mathematical expression

APA, Harvard, Vancouver, ISO, and other styles

9

Goncharov, Sergey, and Andrey Nechesov. "Polynomial Analogue of Gandy’s Fixed Point Theorem." Mathematics 9, no. 17 (2021): 2102. http://dx.doi.org/10.3390/math9172102.

Full text

Abstract:

The paper suggests a general method for proving the fact whether a certain set is p-computable or not. The method is based on a polynomial analogue of the classical Gandy’s fixed point theorem. Classical Gandy’s theorem deals with the extension of a predicate through a special operator ΓΦ(x)Ω∗ and states that the smallest fixed point of this operator is a Σ-set. Our work uses a new type of operator which extends predicates so that the smallest fixed point remains a p-computable set. Moreover, if in the classical Gandy’s fixed point theorem, the special Σ-formula Φ(x¯) is used in the constructi

APA, Harvard, Vancouver, ISO, and other styles

10

Lusk, Ewing, Ralph Butler, and Steven C. Pieper. "Evolution of a minimal parallel programming model." International Journal of High Performance Computing Applications 32, no. 1 (2017): 4–13. http://dx.doi.org/10.1177/1094342017703448.

Full text

Abstract:

We take a historical approach to our presentation of self-scheduled task parallelism, a programming model with its origins in early irregular and nondeterministic computations encountered in automated theorem proving and logic programming. We show how an extremely simple task model has evolved into a system, asynchronous dynamic load balancing (ADLB), and a scalable implementation capable of supporting sophisticated applications on today’s (and tomorrow’s) largest supercomputers; and we illustrate the use of ADLB with a Green’s function Monte Carlo application, a modern, mature nuclear physics

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Automatic theorem proving. Computational complexity"

1

Sabharwal, Ashish. "Algorithmic applications of propositional proof complexity /." Thesis, Connect to this title online; UW restricted, 2005. http://hdl.handle.net/1773/6938.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hertel, Alexander. "Applications of Games to Propositional Proof Complexity." Thesis, 2008. http://hdl.handle.net/1807/16735.

Full text

Abstract:

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer t

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Automatic theorem proving. Computational complexity"

1

Communication complexity: A new approach to circuit depth. MIT Press, 1989.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

2

Efficient checking of polynomials and proofs and the hardness of approximation problems. Springer₋Verlag, 1995.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Makarius, Wenzel, Urban Christian, Nipkow Tobias, and SpringerLink (Online service), eds. Theorem Proving in Higher Order Logics: 22nd International Conference, TPHOLs 2009, Munich, Germany, August 17-20, 2009. Proceedings. Springer Berlin Heidelberg, 2009.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

IJCAR 2010 (2010 Edinburgh, Scotland). Automated reasoning: 5th International Joint Conference, IJCAR 2010, Edinburgh, UK, July 16-19, 2010 : proceedings. Springer, 2010.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Christoph, Zengler, and SpringerLink (Online service), eds. Automated Deduction in Geometry: 7th International Workshop, ADG 2008, Shanghai, China, September 22-24, 2008. Revised Papers. Springer Berlin Heidelberg, 2011.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

1947-, Moore J. Strother, ed. A computational logic handbook. Academic Press, 1988.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

Domenico, Cantone, and Omodeo Eugenio, eds. Computational logic and set theory: Applying formalized logic to analysis. Springer, 2011.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Kurt Gödel Colloquium (3rd 1993 Brno, Czech Republic). Computational logic and proof theory: Third Kurt Gödel Colloquium, KGC'93, Brno, Czech Republic, August 1993 : proceedings. Springer-Verlag, 1993.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

Hiroshi, Nakano, ed. PX, a computational logic. MIT Press, 1988.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

10

G, Gottlob, Leitsch Alexander 1952-, Mundici Daniele 1946-, and Kurt Gödel Society, eds. Computational logic and proof theory: 5th Kurt Gödel Colloquium, KGC '97, Vienna, Austria, August 25-29, 1997 : proceedings. Springer, 1997.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Automatic theorem proving. Computational complexity"

1

Recio, T., and F. Botana. "Where the Truth Lies (in Automatic Theorem Proving in Elementary Geometry)." In Computational Science and Its Applications – ICCSA 2004. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24709-8_80.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Singher, Eytan, and Shachar Itzhaky. "Theory Exploration Powered by Deductive Synthesis." In Computer Aided Verification. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81688-9_6.

Full text

Abstract:

AbstractThis paper presents a symbolic method for automatic theorem generation based on deductive inference. Many software verification and reasoning tasks require proving complex logical properties; coping with this complexity is generally done by declaring and proving relevant sub-properties. This gives rise to the challenge of discovering useful sub-properties that can assist the automated proof process. This is known as the theory exploration problem, and so far, predominant solutions that emerged rely on evaluation using concrete values. This limits the applicability of these theory exploration techniques to complex programs and properties.In this work, we introduce a new symbolic technique for theory exploration, capable of (offline) generation of a library of lemmas from a base set of inductive data types and recursive definitions. Our approach introduces a new method for using abstraction to overcome the above limitations, combining it with deductive synthesis to reason about abstract values. Our implementation has shown to find more lemmas than prior art, avoiding redundant lemmas (in terms of provability), while being faster in most cases. This new abstraction-based theory exploration method is a step toward applying theory exploration to software verification and synthesis.

APA, Harvard, Vancouver, ISO, and other styles

3

Kalai, Gil, and Shmuel Safra. "Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics." In Computational Complexity and Statistical Physics. Oxford University Press, 2005. http://dx.doi.org/10.1093/oso/9780195177374.003.0008.

Full text

Abstract:

Threshold phenomena refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Threshold phenomena play an important role in probability theory and statistics, physics, and computer science, and are related to issues studied in economics and political science. Quite a few questions that come up naturally in those fields translate to proving that some event indeed exhibits a threshold phenomenon, and then finding the location of the transition and how rapid the change is. The notions of sharp thresholds and phase transitions originated in physics, and many of the mathematical ideas for their study came from mathematical physics. In this chapter, however, we will mainly discuss connections to other fields. A simple yet illuminating example that demonstrates the sharp threshold phenomenon is Condorcet's jury theorem, which can be described as follows. Say one is running an election process, where the results are determined by simple majority, between two candidates, Alice and Bob. If every voter votes for Alice with probability p > 1/2 and for Bob with probability 1 — p, and if the probabilities for each voter to vote either way are independent of the other votes, then as the number of voters tends to infinity the probability of Alice getting elected tends to 1. The probability of Alice getting elected is a monotone function of p, and when there are many voters it rapidly changes from being very close to 0 when p < 1/2 to being very close to 1 when p > 1/2. The reason usually given for the interest of Condorcet's jury theorem to economics and political science [535] is that it can be interpreted as saying that even if agents receive very poor (yet independent) signals, indicating which of two choices is correct, majority voting nevertheless results in the correct decision being taken with high probability, as long as there are enough agents, and the agents vote according to their signal. This is referred to in economics as asymptotically complete aggregation of information.

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Automatic theorem proving. Computational complexity"

1

Abdel-Malek, Karim, and Jingzhou Yang. "Method and Code for the Visualization of Multivariate Solids." In ASME 2000 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2000. http://dx.doi.org/10.1115/detc2000/dac-14229.

Full text

Abstract:

Abstract This paper is devoted to a method and computer code for the automatic visualization of multivariate solids. Example of a multivariate solids arise in computer aided geometric design when a geometric entity is swept in space, where the totality of points touched by the entity is called the swept volume and is characterized by an equation of many parameters. The method and code are presented in an integrated manner and are aimed at providing the reader with a replicable computer algorithm. The formulation for is based on the implicit function theorem; is applicable to the visualization

APA, Harvard, Vancouver, ISO, and other styles

2

Escanaverino, Jose Martinez, Jose A. Llamos Soriz, Alejandra Garcia Toll, and Tania Ortiz Cardenas. "Rational Design Automation by Dichromatic Graphs." In ASME 2001 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2001. http://dx.doi.org/10.1115/detc2001/dac-21050.

Full text

Abstract:

Abstract As the complexity of mechanical design increases, due to larger size mathematical models, the need for rational design procedures also goes up. As shown elsewhere, dichromatic graphs have proven their value as tools for the algorithmic education of mechanical engineers. This paper analyzes the worth of such graphs as a means to achieve rational design solutions in complex industrial problems. The paper covers plant maintenance and research & development professional case studies. A real-life problem in electromechanical system reengineering is the first application example. Attent

APA, Harvard, Vancouver, ISO, and other styles

3

Turevsky, Inna, Sankara Hari Gopalakrishnan, and Krishnan Suresh. "Generalization of Topological Sensitivity and Its Application to Defeaturing." In ASME 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2007. http://dx.doi.org/10.1115/detc2007-35353.

Full text

Abstract:

A particularly challenging problem in CAD/CAE is the handling of small geometric details during finite element analysis (FEA). The presence of such details can significantly increase the computational complexity of FEA, while hindering its automation. Therefore, designers typically resort to defeaturing or detail removal, where the offending geometric details are suppressed prior to analysis. However, an inevitable consequence of defeaturing is that it can significantly alter the behavior of the CAE model. In this paper, we address the following question: Given the behavior of the defeatured C

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!