Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
74 | Hervé Fournier, Danièle Gardy, Antoine Genitrini, Marek Zaionc |
Classical and Intuitionistic Logic Are Asymptotically Identical. |
CSL |
2007 |
DBLP DOI BibTeX RDF |
Implicational formulas, Tautologies, Analytic combinatorics, Intuitionistic logic |
67 | Dima Grigoriev |
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. |
FOCS |
1998 |
DBLP DOI BibTeX RDF |
Nullstellensatz proofs, Tseitin's tautologies, lower bounds, expander |
62 | Søren Riis |
A complexity gap for tree resolution. |
Comput. Complex. |
2001 |
DBLP DOI BibTeX RDF |
Logical aspects of complexity, resolution proofs, propositional proof complexity |
56 | Olaf Beyersdorff, Sebastian Müller 0003 |
Does Advice Help to Prove Propositional Tautologies? |
SAT |
2009 |
DBLP DOI BibTeX RDF |
|
56 | Scott Diehl, Dieter van Melkebeek, Ryan Williams 0001 |
An Improved Time-Space Lower Bound for Tautologies. |
COCOON |
2009 |
DBLP DOI BibTeX RDF |
|
56 | Masahiro Kumabe, Toshio Suzuki, Takeshi Yamazaki |
Does truth-table of linear norm reduce the one-query tautologies to a random oracle? |
Arch. Math. Log. |
2008 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000) 68Q15, 03D15 |
56 | Antoine Genitrini, Jakub Kozik, Marek Zaionc |
Intuitionistic vs. Classical Tautologies, Quantitative Comparison. |
TYPES |
2007 |
DBLP DOI BibTeX RDF |
|
56 | Arist Kojevnikov, Dmitry Itsykson |
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies. |
ICALP (1) |
2006 |
DBLP DOI BibTeX RDF |
|
56 | Michael Alekhnovich, Alexander A. Razborov |
Satisfiability, Branch-Width and Tseitin Tautologies. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
56 | Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán |
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. |
STACS |
2000 |
DBLP DOI BibTeX RDF |
|
47 | Moataz Saleh El-Zekey, Wafik Boulos Lotfallah, Nehad N. Morsi |
Computational complexities of axiomatic extensions of monoidal t-norm based logic. |
Soft Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
47 | Antoine Genitrini, Jakub Kozik |
Quantitative Comparison of Intuitionistic and Classical Logics - Full Propositional System. |
LFCS |
2009 |
DBLP DOI BibTeX RDF |
|
42 | Zofia Kostrzycka, Marek Zaionc |
Asymptotic Densities in Logic and Type Theory. |
Stud Logica |
2008 |
DBLP DOI BibTeX RDF |
asymptotic density of tautologies, probabilistic methods in logic and type theory, propositional logic |
42 | Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). |
CCC |
1999 |
DBLP DOI BibTeX RDF |
counting principles, graph tautologies, algebraic proof systems, binomial proofs, Nullstellensatz proofs, polynomial calculus proofs, propositional logic, Proof complexity |
41 | Toshio Suzuki |
Bounded truth table does not reduce the one-query tautologies to a random oracle. |
Arch. Math. Log. |
2005 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000) 68Q15, 03D15 |
41 | Vincent Danos, Jean-Louis Krivine |
Disjunctive Tautologies as Synchronisation Schemes. |
CSL |
2000 |
DBLP DOI BibTeX RDF |
|
41 | Matthias Baaz, Richard Zach |
Short Proofs of Tautologies Using the Schema of Equivalence. |
CSL |
1993 |
DBLP DOI BibTeX RDF |
|
31 | Ran Raz, Iddo Tzameret |
The Strength of Multilinear Proofs. |
Comput. Complex. |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 03F20, 68Q17, 13P10 |
31 | Phuong Nguyen, Stephen A. Cook |
The Complexity of Proving the Discrete Jordan Curve Theorem. |
LICS |
2007 |
DBLP DOI BibTeX RDF |
|
31 | Edward A. Hirsch, Sergey I. Nikolenko |
Simulating Cutting Plane Proofs with Restricted Degree of Falsity by Resolution. |
SAT |
2005 |
DBLP DOI BibTeX RDF |
|
31 | Marcin Mostowski, Konrad Zdanowski |
Degrees of logics with Henkin quantifiers in poor vocabularies. |
Arch. Math. Log. |
2004 |
DBLP DOI BibTeX RDF |
Henkin quantifiers, Degrees of unsolvability |
31 | Phuong Nguyen, Stephen A. Cook |
VTC circ: A Second-Order Theory for TCcirc. |
LICS |
2004 |
DBLP DOI BibTeX RDF |
|
31 | Mauricio Osorio 0001, Fernando Zacarías Flores |
On Updates of Logic Programs: A Properties-Based Approach. |
FoIKS |
2004 |
DBLP DOI BibTeX RDF |
Nelson logic, Update programs, AGM postulates, Answer set programming, Properties, Strong negation |
31 | Vitaly Eltekov |
Checking the Four-Valued Boolean Algebra by the Use PLANNER. |
International Conference on Computational Science |
2003 |
DBLP DOI BibTeX RDF |
|
31 | Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik |
Exponential Lower Bound for Static Semi-algebraic Proofs. |
ICALP |
2002 |
DBLP DOI BibTeX RDF |
|
31 | Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik |
Complexity of Semi-algebraic Proofs. |
STACS |
2002 |
DBLP DOI BibTeX RDF |
|
31 | Ivan Kramosil |
Boolean-like and frequentistic nonstandard semantics for first-order predicate calculus without functions. |
Soft Comput. |
2001 |
DBLP DOI BibTeX RDF |
First-order predicate calculus, Standard semantics, Boolean-like semantics, Frequentistic semantics, Completeness theorems |
31 | Eli Ben-Sasson, Russell Impagliazzo |
Random CNF's are Hard for the Polynomial Calculus. |
FOCS |
1999 |
DBLP DOI BibTeX RDF |
polynomial calculus, satisfiability, proof complexity |
31 | Petr Hájek 0001 |
Basic fuzzy logic and BL-algebras. |
Soft Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
31 | Grazyna Mirkowska |
On the Propositional Algorithmic Logic. |
MFCS |
1979 |
DBLP DOI BibTeX RDF |
|
27 | Paola Bruscoli, Alessio Guglielmi |
On the proof complexity of deep inference. |
ACM Trans. Comput. Log. |
2009 |
DBLP DOI BibTeX RDF |
Frege systems, Statman tautologies, Analyticity, deep inference, calculus of structures |
27 | Zofia Kostrzycka, Marek Zaionc |
Statistics of Intuitionistic versus Classical Logics. |
Stud Logica |
2004 |
DBLP DOI BibTeX RDF |
prepositional logic, asymptotic density of tautologies, probabilistic methods in logic |
27 | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
Pseudorandom Generators in Propositional Proof Complexity. |
FOCS |
2000 |
DBLP DOI BibTeX RDF |
combinatorial pseudorandom generators, Nisan-Wigderson generator, Tseitin tautologies, polynomial calculus with resolution, polynomial calculus, computational complexity, theorem proving, process algebra, resolution, random processes, pseudorandom generators, propositional proof complexity |
25 | Bartosz Wcislo |
Compositional truth with propositional tautologies and quantifier-free correctness. |
Arch. Math. Log. |
2024 |
DBLP DOI BibTeX RDF |
|
25 | Hunter Monroe |
Average-Case Hardness of Proving Tautologies and Theorems. |
Electron. Colloquium Comput. Complex. |
2022 |
DBLP BibTeX RDF |
|
25 | Hunter Monroe |
Average-Case Hardness of Proving Tautologies and Theorems. |
CoRR |
2022 |
DBLP DOI BibTeX RDF |
|
25 | Joshua Blinkhorn |
Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies. |
Electron. Colloquium Comput. Complex. |
2020 |
DBLP BibTeX RDF |
|
25 | Bin Zhao, Jing Lu |
Characteristics and applications of JI, B-implications via some classical logic tautologies. |
Int. J. Approx. Reason. |
2019 |
DBLP DOI BibTeX RDF |
|
25 | Manuel Kauers, Martina Seidl, Doron Zeilberger |
On the maximal minimal cube lengths in distinct DNF tautologies. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
25 | Lorenzo Carlucci, Nicola Galesi, Massimo Lauria |
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies. |
ACM Trans. Comput. Log. |
2016 |
DBLP DOI BibTeX RDF |
|
25 | Vasil Sgurev |
Formulae, tautologies, and equipotences in the complex s-logic. |
IEEE Conf. on Intelligent Systems |
2016 |
DBLP DOI BibTeX RDF |
|
25 | Olena Yaskorska, Katarzyna Budzynska, Magdalena Kacprzak |
Proving Propositional Tautologies in a Natural Dialogue. |
Fundam. Informaticae |
2013 |
DBLP DOI BibTeX RDF |
|
25 | Leszek Jaworski |
From the research on logics without tautologies (part 2). |
Log. J. IGPL |
2013 |
DBLP DOI BibTeX RDF |
|
25 | Leszek Jaworski |
From the research on logics without tautologies (part 3). |
Log. J. IGPL |
2013 |
DBLP DOI BibTeX RDF |
|
25 | Leszek Jaworski |
From the research on logics without tautologies (part 1). |
Log. J. IGPL |
2013 |
DBLP DOI BibTeX RDF |
|
25 | László Aszalós, Tamás Herendi |
Density of Tautologies in Logics with One Variable. |
Acta Cybern. |
2012 |
DBLP DOI BibTeX RDF |
|
25 | Huawen Liu |
On a New Class of Implications: (G, Min)-Implications and Several Classical Tautologies. |
Int. J. Uncertain. Fuzziness Knowl. Based Syst. |
2012 |
DBLP DOI BibTeX RDF |
|
25 | Jan Krajícek |
On the computational complexity of finding hard tautologies |
CoRR |
2012 |
DBLP BibTeX RDF |
|
25 | Antoine Genitrini, Jakub Kozik |
In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid. |
Ann. Pure Appl. Log. |
2012 |
DBLP DOI BibTeX RDF |
|
25 | Michael Alekhnovich, Alexander A. Razborov |
Satisfiability, Branch-Width and Tseitin tautologies. |
Comput. Complex. |
2011 |
DBLP DOI BibTeX RDF |
|
25 | Scott Diehl, Dieter van Melkebeek, Ryan Williams 0001 |
An improved time-space lower bound for tautologies. |
J. Comb. Optim. |
2011 |
DBLP DOI BibTeX RDF |
|
25 | Lorenzo Carlucci, Nicola Galesi, Massimo Lauria |
Paris-Harrington Tautologies. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
25 | Hervé Fournier, Danièle Gardy, Antoine Genitrini, Marek Zaionc |
Tautologies over implication with negative literals. |
Math. Log. Q. |
2010 |
DBLP DOI BibTeX RDF |
|
25 | Lorenzo Carlucci, Nicola Galesi, Massimo Lauria |
Paris-Harrington tautologies. |
Electron. Colloquium Comput. Complex. |
2010 |
DBLP BibTeX RDF |
|
25 | Petr Hájek 0001 |
Some (non)tautologies of łukasiewicz and Product Logic. |
Rev. Symb. Log. |
2010 |
DBLP DOI BibTeX RDF |
|
25 | Stefan Hetzl |
Describing proofs by short tautologies. |
Ann. Pure Appl. Log. |
2009 |
DBLP DOI BibTeX RDF |
|
25 | Balázs Szörényi |
Disjoint DNF Tautologies with Conflict Bound Two. |
J. Satisf. Boolean Model. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
25 | Jan Krajícek |
Substitutions into propositional tautologies. |
Inf. Process. Lett. |
2007 |
DBLP DOI BibTeX RDF |
|
25 | J. Balasubramaniam 0001 |
Yager's new class of implications Jf and some classical tautologies. |
Inf. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
25 | Benjamín René Callejas Bedregal |
A normal form which preserves tautologies and contradictions in a class of fuzzy logics. |
J. Algorithms |
2007 |
DBLP DOI BibTeX RDF |
|
25 | Samuel R. Buss |
Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies. |
Theor. Comput. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
25 | Marek Zaionc |
Probability distribution for simple tautologies. |
Theor. Comput. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
25 | Jan Krajícek |
Structured pigeonhole principle, search problems and hard tautologies. |
J. Symb. Log. |
2005 |
DBLP DOI BibTeX RDF |
|
25 | Marek Zaionc |
On the Asymptotic Density of Tautologies in Logic of Implication and Negation. |
Reports Math. Log. |
2005 |
DBLP BibTeX RDF |
|
25 | Benjamín René Callejas Bedregal, Regivan H. N. Santiago, Anne Magály de Paula Canuto |
A normal form which preserves 1-tautologies and 0-contradictions in a class of residuum-based propositional fuzzy logics. |
FUZZ-IEEE |
2004 |
DBLP DOI BibTeX RDF |
|
25 | Jan Krajícek |
Tautologies from pseudo-random generators. |
Bull. Symb. Log. |
2001 |
DBLP DOI BibTeX RDF |
|
25 | Matthias Baaz, Petr Hájek 0001, Franco Montagna, Helmut Veith |
Complexity of t-tautologies. |
Ann. Pure Appl. Log. |
2001 |
DBLP DOI BibTeX RDF |
|
25 | Stefan S. Dantchev, Søren Riis |
"Planar" Tautologies Hard for Resolution. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
25 | Toshio Suzuki |
Complexity of the r-query Tautologies in the Presence of a Generic Oracle. |
Notre Dame J. Formal Log. |
2000 |
DBLP DOI BibTeX RDF |
|
25 | Petr Savický, Jirí Sgall |
DNF tautologies with a limited number of occurrences of every variable. |
Theor. Comput. Sci. |
2000 |
DBLP DOI BibTeX RDF |
|
25 | Jan Krajícek |
Tautologies from pseudo-random generators |
Electron. Colloquium Comput. Complex. |
2000 |
DBLP BibTeX RDF |
|
25 | Søren Riis, Meera Sitharam |
Generating hard tautologies using predicate logic and the symmetric group. |
Log. J. IGPL |
2000 |
DBLP DOI BibTeX RDF |
|
25 | Wolfgang Bibel, Elmar Eder |
Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution. |
J. ACM |
1997 |
DBLP DOI BibTeX RDF |
connection-graph resolution, decomposition of unsatisfiable formulas, semantic trees, regular graphs, strong completeness |
25 | Jeremy Avigad |
Plausibly hard combinatorial tautologies. |
Proof Complexity and Feasible Arithmetics |
1996 |
DBLP DOI BibTeX RDF |
|
25 | Michael Bertol, Klaus Reinhardt |
The Tautologies over a Finite Set are Context-Free. |
Bull. EATCS |
1995 |
DBLP BibTeX RDF |
|
25 | Uwe Egly |
Super-Polynomial Speed-Ups in Proof Length by New Tautologies. |
EPIA |
1995 |
DBLP DOI BibTeX RDF |
|
25 | Gennady Davydov, Inna Davydova |
Tautologies and Positive Solvability of Linear Homogeneous Systems. |
Ann. Pure Appl. Log. |
1992 |
DBLP DOI BibTeX RDF |
|
25 | Wieslaw Dziobiak |
A Finite Matrix Whose Set of Tautologies Is Not Finitely Axiomatizable. |
Reports Math. Log. |
1991 |
DBLP BibTeX RDF |
|
25 | Daniele Mundici |
Tautologies with a unique craig interpolant, uniform vs. nonuniform complexity. |
Ann. Pure Appl. Log. |
1984 |
DBLP DOI BibTeX RDF |
|
25 | Balakrishnan Krishnamurthy, Robert N. Moll |
Examples of Hard Tautologies in the Propositional Calculus |
STOC |
1981 |
DBLP DOI BibTeX RDF |
|
25 | Leo Simons |
More logics without tautologies. |
Notre Dame J. Formal Log. |
1978 |
DBLP DOI BibTeX RDF |
|
25 | Alan Rose |
A Note on the Existence of Tautologies in Certain Propositional Calculi Without Propositional Variables. |
Math. Log. Q. |
1976 |
DBLP DOI BibTeX RDF |
|
25 | Alan Rose |
A note on the existence of tautologies without constants. |
Math. Log. Q. |
1975 |
DBLP DOI BibTeX RDF |
|
25 | Leo Simons |
Logic without tautologies. |
Notre Dame J. Formal Log. |
1974 |
DBLP DOI BibTeX RDF |
|
25 | M. Bauer, D. Brand, Michael J. Fischer, Albert R. Meyer, Mike Paterson |
A note on disjunctive form tautologies. |
SIGACT News |
1973 |
DBLP DOI BibTeX RDF |
|
25 | Gerald Standley |
Testing Singly Quantified Tautologies. |
J. Symb. Log. |
1966 |
DBLP DOI BibTeX RDF |
|
25 | Jan Kalicki |
A Test for the Existence of Tautologies According to Many-Valued Truth-Tables. |
J. Symb. Log. |
1950 |
DBLP DOI BibTeX RDF |
|
16 | Søren Riis |
On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity. |
LICS |
2008 |
DBLP DOI BibTeX RDF |
Algebraic proof complexity, predicate logic, Propositional proof complexity |
16 | Dragan G. Radojevic, Aleksandar Perovic, Zoran Ognjanovic, Miodrag Raskovic |
Interpolative Boolean Logic. |
AIMSA |
2008 |
DBLP DOI BibTeX RDF |
|
16 | Zofia Kostrzycka |
The density of truth in monadic fragments of some intermediate logics. |
J. Log. Lang. Inf. |
2007 |
DBLP DOI BibTeX RDF |
Density of truth, Medvedev’s logic, Linear logic, Generating functions |
16 | Manuel Clavel, Francisco Durán 0001, Steven Eker, Patrick Lincoln, Narciso Martí-Oliet, José Meseguer 0001, Carolyn L. Talcott |
LTL Model Checking. |
All About Maude |
2007 |
DBLP DOI BibTeX RDF |
|
16 | Pedro Cabalar, David Pearce 0001, Agustín Valverde |
Minimal Logic Programs. |
ICLP |
2007 |
DBLP DOI BibTeX RDF |
minimisation of boolean and multivalued functions, logic programming, answer set programming |
16 | Zbigniew Bonikowski, Urszula Wybraniec-Skardowska |
Rough Sets and Vague Sets. |
RSEISP |
2007 |
DBLP DOI BibTeX RDF |
|
16 | Alexis Maciel, Toniann Pitassi |
Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives. |
LICS |
2006 |
DBLP DOI BibTeX RDF |
|
16 | Stefan S. Dantchev |
Relativisation Provides Natural Separations for Resolution-Based Proof Systems. |
CSR |
2006 |
DBLP DOI BibTeX RDF |
|
16 | Arist Kojevnikov, Alexander S. Kulikov |
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. |
SAT |
2006 |
DBLP DOI BibTeX RDF |
|
16 | Jan Krajícek |
Forcing with Random Variables and Proof Complexity. |
CiE |
2006 |
DBLP DOI BibTeX RDF |
|
16 | DoRon B. Motter, Jarrod A. Roy, Igor L. Markov |
Resolution cannot polynomially simulate compressed-BFS. |
Ann. Math. Artif. Intell. |
2005 |
DBLP DOI BibTeX RDF |
|
16 | Petr Hájek 0001 |
Arithmetical complexity of fuzzy predicate logics - a survey. |
Soft Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
16 | Jan Rauch |
Logic of Association Rules. |
Appl. Intell. |
2005 |
DBLP DOI BibTeX RDF |
GUHA method, 4ft-Miner procedure, data mining, association rules, mathematical logic |