Search results for "Tautologies"

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