Search results for "relativization"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
114	Joseph S. Miller, Lawrence S. Moss	The Undecidability of Iterated Modal Relativization.	Stud Logica	2005	DBLP DOI BibTeX RDF	iterated relativization, modal logic, undecidability, Dynamic epistemic logic
106	Jin-yi Cai, Osamu Watanabe 0001	Stringent Relativization.	FSTTCS	2003	DBLP DOI BibTeX RDF
53	Baris Aydinlioglu, Eric Bach 0001	Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers.	ACM Trans. Comput. Theory	2019	DBLP DOI BibTeX RDF
53	Baris Aydinlioglu, Eric Bach 0001	Affine Relativization: Unifying the Algebrization and Relativization Barriers.	ACM Trans. Comput. Theory	2018	DBLP DOI BibTeX RDF
53	Baris Aydinlioglu, Eric Bach 0001	Affine Relativization: Unifying the Algebrization and Relativization Barriers.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
48	Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova	An axiomatic approach to algebrization.	STOC	2009	DBLP DOI BibTeX RDF	algebrization, independence, relativization
46	Lawrence S. Moss, Satish R. Thatte	Generalization of Final Algebra Semantics by Relativization.	Mathematical Foundations of Programming Semantics	1989	DBLP DOI BibTeX RDF
40	Scott Aaronson, Avi Wigderson	Algebrization: a new barrier in complexity theory.	STOC	2008	DBLP DOI BibTeX RDF	communication complexity, oracles, arithmetization, interactive proofs, query complexity, low-degree polynomials
40	Claudio Ferretti, Giancarlo Mauri	Remarks on Relativisations and DNA Encodings.	Aspects of Molecular Computing	2004	DBLP DOI BibTeX RDF
40	Jin-yi Cai, Osamu Watanabe 0001	On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.	COCOON	2003	DBLP DOI BibTeX RDF
40	Juris Hartmanis, Lane A. Hemachandra	On Sparse Oracles Separating Feasible Complexity Classes.	STACS	1986	DBLP DOI BibTeX RDF
28	Jeong Han Kim, Daniel R. Simon, Prasad Tetali	Limits on the Efficiency of One-Way Permutation-Based Hash Functions.	FOCS	1999	DBLP DOI BibTeX RDF	cryptography, Oracle, complexity theory, relativization
28	Heribert Vollmer, Klaus W. Wagner	On Operators of Higher Types.	CCC	1997	DBLP DOI BibTeX RDF	set operator vs. word operator, translational methods, oracle, Operator, interactive protocol, relativization
28	Georg Gottlob	Collapsing Oracle-Tape Hierarchies.	CCC	1996	DBLP DOI BibTeX RDF	tape, logspace, logarithmic space, machine model, complexity, query, oracle, circuit, Turing machine, generalized quantifier, relativization, bounded queries
27	Andrei Popescu 0001, Dmitriy Traytel	Admissible Types-to-PERs Relativization in Higher-Order Logic.	Proc. ACM Program. Lang.	2023	DBLP DOI BibTeX RDF
27	Shuichi Hirahara, Zhenjian Lu, Hanlin Ren	Bounded Relativization.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
27	Wesley Calvert, Emma Grunner, Elvira Mayordomo, Daniel Turetsky, Java Darleen Villano	Normality, Relativization, and Randomness.	CoRR	2023	DBLP DOI BibTeX RDF
27	Gijs Wijnholds, Michael Moortgat	Structural Ambiguity and its Disambiguation in Language Model Based Parsers: the Case of Dutch Clause Relativization.	CoRR	2023	DBLP DOI BibTeX RDF
27	Gijs Wijnholds, Michael Moortgat	Structural Ambiguity and its Disambiguation in Language Model Based Parsers: the Case of Dutch Clause Relativization.	CoNLL	2023	DBLP DOI BibTeX RDF
27	Shuichi Hirahara, Zhenjian Lu, Hanlin Ren	Bounded Relativization.	CCC	2023	DBLP DOI BibTeX RDF
27	Rabanus Derr, Robert C. Williamson	Fairness and Randomness in Machine Learning: Statistical Independence and Relativization.	CoRR	2022	DBLP DOI BibTeX RDF
27	Hanlin Ren, Rahul Santhanam	A Relativization Perspective on Meta-Complexity.	STACS	2022	DBLP DOI BibTeX RDF
27	Hanlin Ren, Rahul Santhanam	A Relativization Perspective on Meta-Complexity.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
27	Tianrong Lin	On Baker-Gill-Solovay Oracle Turing Machines and Relativization Barrier.	CoRR	2021	DBLP BibTeX RDF
27	Quyen Nguyen	Island effects in Vietnamese relativization: A formal judgment study.	PACLIC	2021	DBLP BibTeX RDF
27	Ian Briggs, Arnab Das, Mark Baranowski, Vishal Chandra Sharma, Sriram Krishnamoorthy, Zvonimir Rakamaric, Ganesh Gopalakrishnan	FailAmp: Relativization Transformation for Soft Error Detection in Structured Address Generation.	ACM Trans. Archit. Code Optim.	2020	DBLP DOI BibTeX RDF
27	Anatole Dahan, Anuj Dawar	Relativization of Gurevich's Conjectures.	CoRR	2020	DBLP BibTeX RDF
27	Anatole Dahan, Anuj Dawar	Relativization of Gurevich's Conjectures.	Fields of Logic and Computation III	2020	DBLP DOI BibTeX RDF
27	Kenshi Miyabe	Uniform Relativization.	CiE	2019	DBLP DOI BibTeX RDF
27	Ralph Christian Bottesch	Relativization and Interactive Proof Systems in Parameterized Complexity Theory.	CoRR	2017	DBLP BibTeX RDF
27	Antonín Dvorák, Michal Holcapek	Relativization of Fuzzy Quantifiers: Initial Investigations.	EUSFLAT/IWIFSGN (1)	2017	DBLP DOI BibTeX RDF
27	Ralph Bottesch	Relativization and Interactive Proof Systems in Parameterized Complexity Theory.	IPEC	2017	DBLP DOI BibTeX RDF
27	Xin Kou	Comitative Relational Nouns and Relativization of Comitative Case in Mandarin.	CLSW	2016	DBLP DOI BibTeX RDF
27	Stefan S. Dantchev, Barnaby Martin	Relativization makes contradictions harder for Resolution.	Ann. Pure Appl. Log.	2014	DBLP DOI BibTeX RDF
27	Francesco Alberti, Silvio Ghilardi, Elena Pagani, Silvio Ranise, Gian Paolo Rossi 0001	Universal Guards, Relativization of Quantifiers, and Failure Models in Model Checking Modulo Theories.	J. Satisf. Boolean Model. Comput.	2012	DBLP DOI BibTeX RDF
27	Andrei A. Muchnik, Andrei E. Romashchenko	Stability of properties of Kolmogorov complexity under relativization.	Probl. Inf. Transm.	2010	DBLP DOI BibTeX RDF
27	André Nies, Frank Stephan 0001, Sebastiaan Terwijn	Randomness, relativization and Turing degrees.	J. Symb. Log.	2005	DBLP DOI BibTeX RDF
27	Holger Spakowski, Rahul Tripathi	Degree Bounds on Polynomials and Relativization Theory.	IFIP TCS	2004	DBLP DOI BibTeX RDF
27	Lance Fortnow	The Role of Relativization in Complexity Theory.	Bull. EATCS	1994	DBLP BibTeX RDF
27	Harry Buhrman, Leen Torenvliet	On the Cutting Edge of Relativization: The Resource Bounded Injury Method.	ICALP	1994	DBLP DOI BibTeX RDF
27	Ricard Gavaldà	A Positive Relativization of Polynomial Time Versus Polylog Space.	Inf. Process. Lett.	1993	DBLP DOI BibTeX RDF
27	Stefano Stefani	A Relativization Mechanism in Recursion Categories.	J. Symb. Log.	1993	DBLP DOI BibTeX RDF
27	Juris Hartmanis, Richard Chang 0001, Suresh Chari, Desh Ranjan, Pankaj Rohatgi	Relativization: a Revisionistic Retrospective.	Current Trends in Theoretical Computer Science	1993	DBLP DOI BibTeX RDF
27	Juris Hartmanis, Richard Chang 0001, Jim Kadin, Stephen G. Mitchell	Some Observations about Relativization of Space Bounded Computations.	Current Trends in Theoretical Computer Science	1993	DBLP DOI BibTeX RDF
27	Richard Chang 0001, Suresh Chari, Desh Ranjan, Pankaj Rohatgi	Relativization: a revisionistic retrospective.	Bull. EATCS	1992	DBLP BibTeX RDF
27	Hidetosi Sirai, Yutaka Tomioka	Syntactic Constraints On Relativization In Japanese.	COLING	1992	DBLP BibTeX RDF
27	Richard Chang 0001	An Example of a Theorem that has Contradictory Relativization and Diagonalization Proof.	Bull. EATCS	1990	DBLP BibTeX RDF
27	Bernd Kirsig, Klaus-Jörn Lange	Separation with the Ruzzo, Simon, and Tompa Relativization Implies DSPACE(log n) != NSPACE(log n).	Inf. Process. Lett.	1987	DBLP DOI BibTeX RDF
27	Nobuyoshi Motohashi	Preservation Theorem and Relativization Theorem For Cofinal Extensions.	J. Symb. Log.	1986	DBLP DOI BibTeX RDF
27	Antonio Di Nola, Aldo G. S. Ventre	A relativization of the concept of synthesis in fuzzy set theory.	Inf. Sci.	1984	DBLP DOI BibTeX RDF
27	Michael Sipser	On Relativization and the Existence of Complete Sets.	ICALP	1982	DBLP DOI BibTeX RDF
27	Masazumi Hanazawa	An Extension of the Notion of Relativization to Hilbert's ϵ-Symbol.	Math. Log. Q.	1980	DBLP DOI BibTeX RDF
27	Richard E. Ladner, Nancy A. Lynch	Relativization of Questions About Log Space Computability.	Math. Syst. Theory	1976	DBLP DOI BibTeX RDF
27	Michael I. Dekhtyar	On the Relativization of Deterministic and Nondeterministic Complexity Classes.	MFCS	1976	DBLP DOI BibTeX RDF
20	Zoran Majkic, Bhanu Prasad 0001	Soft Query-Answering Computing in P2P Systems with Epistemically Independent Peers.	Soft Computing Applications in Industry	2008	DBLP DOI BibTeX RDF
20	Mark Steedman	The Grammar of Scope.	WoLLIC	2008	DBLP DOI BibTeX RDF
20	Jin-yi Cai, Osamu Watanabe 0001	Random Access to Advice Strings and Collapsing Results.	Algorithmica	2006	DBLP DOI BibTeX RDF
20	Josef Urban	MPTP 0.2: Design, Implementation, and Initial Experiments.	J. Autom. Reason.	2006	DBLP DOI BibTeX RDF	MPTP, Mizar, ATP, MPA, re-proving, proof discovery, MML
20	Jin-yi Cai, Osamu Watanabe 0001	Random Access to Advice Strings and Collapsing Results.	ISAAC	2004	DBLP DOI BibTeX RDF
20	Peter A. Fejer, Richard A. Shore	Every incomplete computably enumerable truth-table degree is branching.	Arch. Math. Log.	2001	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03D30, 03D25
20	Steven Homer, Sarah Mocas	Nonuniform Lower Bounds for Exponential Time Classes.	MFCS	1995	DBLP DOI BibTeX RDF
20	Bernd Borchert	On the Acceptance Power of Regular Languages.	STACS	1994	DBLP DOI BibTeX RDF
20	Johann A. Makowsky, Y. B. Pnueli	Oracles and Quantifiers.	CSL	1993	DBLP DOI BibTeX RDF
20	Ricard Gavaldà, José L. Balcázar	Strong and Robustly Strong Polynomial Time Reducibilities to Sparse Sets.	MFCS	1988	DBLP DOI BibTeX RDF
20	Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra	On Generating Solved Instances of Computational Problems.	CRYPTO	1988	DBLP DOI BibTeX RDF
20	Juris Hartmanis, Neil Immerman	On Complete Problems for NP$\cap$CoNP.	ICALP	1985	DBLP DOI BibTeX RDF