Search results for "PTIME"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
129	Alan Nash, Jeffrey B. Remmel, Victor Vianu	PTIME Queries Revisited.	ICDT	2005	DBLP DOI BibTeX RDF
87	Andrzej S. Murawski, C.-H. Luke Ong	Discreet Games, Light Affine Logic and PTIME Computation.	CSL	2000	DBLP DOI BibTeX RDF	PTIME, Complexity, Linear Logic, Game Semantics
65	Harry G. Mairson, Kazushige Terui	On the Computational Complexity of Cut-Elimination in Linear Logic.	ICTCS	2003	DBLP DOI BibTeX RDF
64	Linh Anh Nguyen	Approximating Horn Knowledge Bases in Regular Description Logics to Have PTIME Data Complexity.	ICLP	2007	DBLP DOI BibTeX RDF
52	Pauline Berry, Bart Peintner, Ken Conley, Melinda T. Gervasio, Tomás E. Uribe, Neil Yorke-Smith	Deploying a personalized time management agent.	AAMAS	2006	DBLP DOI BibTeX RDF	scheduling, user interfaces, deployment, personal assistants
51	David Van Horn, Harry G. Mairson	Flow Analysis, Linearity, and PTIME.	SAS	2008	DBLP DOI BibTeX RDF
51	Manizheh Montazerian, Peter T. Wood, Seyed R. Mousavi	XPath Query Satisfiability is in PTIME for Real-World DTDs.	XSym	2007	DBLP DOI BibTeX RDF	Document Type Definitions, Satisfiability, XPath
51	Guillaume Bonfante	Some Programming Languages for Logspace and Ptime.	AMAST	2006	DBLP DOI BibTeX RDF
51	Vladimir Yu. Sazonov, Alexei Lisitsa 0001	Delta-Languages for Sets and sub-PTIME Graphs Transformers.	ICDT	1995	DBLP DOI BibTeX RDF
39	Avigdor Gal, Maria Vanina Martinez, Gerardo I. Simari, V. S. Subrahmanian	Aggregate Query Answering under Uncertain Schema Mappings.	ICDE	2009	DBLP DOI BibTeX RDF
39	Peter T. Wood	Containment for XPath Fragments under DTD Constraints.	ICDT	2003	DBLP BibTeX RDF
39	Manolis Koubarakis, Spiros Skiadopoulos	Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatiotemporal Information.	Spatio-Temporal Database Management	1999	DBLP DOI BibTeX RDF
39	Tomasz Imielinski, Kumar V. Vadaparty	Complexity of Query Processing in Databases with OR-Objects.	PODS	1989	DBLP DOI BibTeX RDF
38	Vincent Atassi, Patrick Baillot, Kazushige Terui	Verification of Ptime Reducibility for System F Terms Via Dual Light Affine Logic.	CSL	2006	DBLP DOI BibTeX RDF
38	Luca Corciulo, Fosca Giannotti, Dino Pedreschi	Datalog with Non-Deterministic Choice Computes NDB-PTIME.	DOOD	1993	DBLP DOI BibTeX RDF
26	Wolfgang Gatterbauer, Dan Suciu	Data conflict resolution using trust mappings.	SIGMOD Conference	2010	DBLP DOI BibTeX RDF	community database, consistency, data exchange, stable model
26	David Zook, Emir Pasalic, Beata Sarna-Starosta	Typed Datalog.	PADL	2009	DBLP DOI BibTeX RDF	Meta-compilation, Type System, Datalog, Deductive Databases
26	Abhay Kumar Jha, Vibhor Rastogi, Dan Suciu	Query evaluation with soft-key constraints.	PODS	2008	DBLP DOI BibTeX RDF	query processing, probabilistic databases
26	Nilesh N. Dalvi, Dan Suciu	The dichotomy of conjunctive queries on probabilistic structures.	PODS	2007	DBLP DOI BibTeX RDF	probabilistic databases, conjunctive queries, dichotomy
26	Marcin Jurdzinski, François Laroussinie, Jeremy Sproston	Model Checking Probabilistic Timed Automata with One or Two Clocks.	TACAS	2007	DBLP DOI BibTeX RDF
26	Marco Gaboardi, Simona Ronchi Della Rocca	A Soft Type Assignment System for lambda -Calculus.	CSL	2007	DBLP DOI BibTeX RDF
26	Henrik Björklund, Wim Martens, Thomas Schwentick	Conjunctive Query Containment over Trees.	DBPL	2007	DBLP DOI BibTeX RDF
26	Georg Gottlob, Christoph Koch 0001, Reinhard Pichler, Luc Segoufin	The complexity of XPath query evaluation and XML typing.	J. ACM	2005	DBLP DOI BibTeX RDF	LOGCFL, XML, Complexity, XPath, DTD
26	Weirong Wang, Aloysius K. Mok, Gerhard Fohler	Pre-Scheduling on the Domain of Integers.	RTSS	2004	DBLP DOI BibTeX RDF
26	Régis Barbanchon, Etienne Grandjean	The Minimal Logically-Defined NP-Complete Problem.	STACS	2004	DBLP DOI BibTeX RDF	Computational complexity, NP-completeness, descriptive complexity, finite model theory, parsimony, second-order logic
26	Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi	View-Based Query Processing and Constraint Satisfaction.	LICS	2000	DBLP DOI BibTeX RDF	view-based query answering, view-based query rewriting, databases, constraint satisfaction, semistructured data
26	Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer 0001	Hyper-Polynomial Hierarchies and the NP-Jump.	CCC	1997	DBLP DOI BibTeX RDF
26	Hans Leiß	Bounded Fixed-Point Definability and Tabular Recognition of Languages.	CSL	1995	DBLP DOI BibTeX RDF
26	Paris C. Kanellakis, Gerd G. Hillebrand, Harry G. Mairson	An Analysis of the Core-ML Language: Expressive Power and Type Reconstruction.	ICALP	1994	DBLP DOI BibTeX RDF
26	Arnold Schönhage	On the Power of Random Access Machines.	ICALP	1979	DBLP DOI BibTeX RDF
26	Juris Hartmanis, Theodore P. Baker	Relative Succinctness of Representations of Languages and Separation of Complexity Classes.	MFCS	1979	DBLP DOI BibTeX RDF
25	Siddharth Bhaskar, Cynthia Kop, Jakob Grue Simonsen	Subclasses of Ptime Interpreted by Programming Languages.	Theory Comput. Syst.	2023	DBLP DOI BibTeX RDF
25	Eugenia Ternovska	Towards Capturing PTIME with no Counting Construct (but with a Choice Operator).	CoRR	2021	DBLP BibTeX RDF
25	Neil D. Jones, Siddharth Bhaskar, Cynthia Kop, Jakob Grue Simonsen	Cons-free Programs and Complexity Classes between LOGSPACE and PTIME.	VPT/HCVS@ETAPS	2020	DBLP DOI BibTeX RDF
25	Utkarsh Gupta, Preey Shah, S. Akshay 0001, Piotr Hofman	Continuous Reachability for Unordered Data Petri nets is in PTime.	CoRR	2019	DBLP BibTeX RDF
25	Utkarsh Gupta, Preey Shah, S. Akshay 0001, Piotr Hofman	Continuous Reachability for Unordered Data Petri Nets is in PTime.	FoSSaCS	2019	DBLP DOI BibTeX RDF
25	Pablo Barceló, Cristina Feier, Carsten Lutz, Andreas Pieris	PTime Combined Complexity and FPT in Ontology-Mediated Querying.	Description Logics	2019	DBLP BibTeX RDF
25	Tomás Masopust	Separability by piecewise testable languages is PTime-complete.	Theor. Comput. Sci.	2018	DBLP DOI BibTeX RDF
25	André Hernich, Carsten Lutz, Fabio Papacchini, Frank Wolter	Horn-Rewritability vs PTime Query Evaluation in Ontology-Mediated Querying.	IJCAI	2018	DBLP DOI BibTeX RDF
25	Cynthia Kop	On First-order Cons-free Term Rewriting and PTIME.	CoRR	2017	DBLP BibTeX RDF
25	Tomás Masopust	Separability by Piecewise Testable Languages is PTime-Complete.	CoRR	2017	DBLP BibTeX RDF
25	André Hernich, Carsten Lutz, Fabio Papacchini, Frank Wolter	Horn Rewritability vs PTime Query Answering for Description Logic TBoxes.	Description Logics	2017	DBLP BibTeX RDF
25	Kenneth R. Blaney, Andrey Nikolaev	A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups.	Groups Complex. Cryptol.	2016	DBLP BibTeX RDF
25	Clément Aubert, Marc Bagnol, Thomas Seiller	Unary Resolution: Characterizing Ptime.	FoSSaCS	2016	DBLP DOI BibTeX RDF
25	Filip Konecný	PTIME Computation of Transitive Closures of Octagonal Relations.	TACAS	2016	DBLP DOI BibTeX RDF
25	Clément Aubert, Marc Bagnol, Thomas Seiller	Memoization for Unary Logic Programming: Characterizing PTIME.	CoRR	2015	DBLP BibTeX RDF
25	Patrick Baillot	On the expressivity of elementary linear logic: Characterizing Ptime and an exponential time hierarchy.	Inf. Comput.	2015	DBLP DOI BibTeX RDF
25	Filip Konecný	PTIME Computation of Transitive Closures of Octagonal Relations.	CoRR	2014	DBLP BibTeX RDF
25	David Van Horn, Harry G. Mairson	Flow analysis, linearity, and PTIME.	CoRR	2013	DBLP BibTeX RDF
25	Jakub Szymanik	Backward Induction Is PTIME-complete.	LORI	2013	DBLP DOI BibTeX RDF
25	Barbara Dunin-Keplicz, Linh Anh Nguyen, Andrzej Szalas	Horn-TeamLog: A Horn Fragment of TeamLog with PTime Data Complexity.	ICCCI	2013	DBLP DOI BibTeX RDF
25	David Toman 0001, Grant E. Weddell	CFDnc: A PTIME Description Logic with Functional Constraints and Disjointness.	Description Logics	2013	DBLP BibTeX RDF
25	Linh Anh Nguyen, Thi-Bich-Loc Nguyen, Andrzej Szalas	HornDL: An Expressive Horn Description Logic with PTime Data Complexity.	RR	2013	DBLP DOI BibTeX RDF
25	David Toman 0001, Grant E. Weddell	Conjunctive Query Answering in CFDnc : A PTIME Description Logic with Functional Constraints and Disjointness.	Australasian Conference on Artificial Intelligence	2013	DBLP DOI BibTeX RDF
25	Jacek Chrzaszcz, Aleksy Schubert	ML with PTIME complexity guarantees.	CSL	2012	DBLP DOI BibTeX RDF
25	Pauline M. Berry, Melinda T. Gervasio, Bart Peintner, Neil Yorke-Smith	PTIME: Personalized assistance for calendaring.	ACM Trans. Intell. Syst. Technol.	2011	DBLP DOI BibTeX RDF
25	Werner Damm, Carsten Ihlemann, Viorica Sofronie-Stokkermans	PTIME Parametric Verification of Safety Properties for Reasonable Linear Hybrid Automata.	Math. Comput. Sci.	2011	DBLP DOI BibTeX RDF
25	Linh Anh Nguyen	Horn Knowledge Bases in Regular Description Logics with PTIME Data Complexity.	Fundam. Informaticae	2010	DBLP DOI BibTeX RDF
25	Yijia Chen, Jörg Flum	On optimal proof systems and logics for PTIME.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
25	Aloïs Brunel, Kazushige Terui	Church => Scott = Ptime: an application of resource sensitive realizability	DICE	2010	DBLP DOI BibTeX RDF
25	Yijia Chen, Jörg Flum	On p-Optimal Proof Systems and Logics for PTIME.	ICALP (2)	2010	DBLP DOI BibTeX RDF
25	Yijia Chen, Jörg Flum	A Logic for PTIME and a Parameterized Halting Problem.	Fields of Logic and Computation	2010	DBLP DOI BibTeX RDF
25	Yijia Chen, Jörg Flum	A Logic for PTIME and a Parameterized Halting Problem.	LICS	2009	DBLP DOI BibTeX RDF
25	Michael J. Burrell, J. Robin B. Cockett, Brian F. Redmond	Pola: A Language for PTIME Programming.	FICS	2009	DBLP BibTeX RDF
25	David Toman 0001, Grant E. Weddell	Applications and Extensions of PTIME Description Logics with Functional Constraints.	IJCAI	2009	DBLP BibTeX RDF
25	Yijia Chen, Jörg Flum	A logic for PTIME and a parameterized halting problem.	Electron. Colloquium Comput. Complex.	2008	DBLP BibTeX RDF
25	Martin Grohe	The Quest for a Logic Capturing PTIME.	LICS	2008	DBLP DOI BibTeX RDF	query languages, descriptive complexity, finite model theory
25	Florian Horn 0001	Explicit Muller Games are PTIME.	FSTTCS	2008	DBLP DOI BibTeX RDF
25	Vincent Atassi, Patrick Baillot, Kazushige Terui	Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic	CoRR	2007	DBLP BibTeX RDF
25	Vincent Atassi, Patrick Baillot, Kazushige Terui	Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic.	Log. Methods Comput. Sci.	2007	DBLP DOI BibTeX RDF
25	Vincent Atassi, Patrick Baillot, Kazushige Terui	Verification of Ptime reducibility for system F terms via Dual Light Affine Logic	CoRR	2006	DBLP BibTeX RDF
25	Zdenek Sawa, Petr Jancar	Behavioural Equivalences on Finite-State Systems are PTIME-hard.	Comput. Artif. Intell.	2005	DBLP BibTeX RDF
25	Nicolas Markey, Philippe Schnoebelen	A PTIME-complete matching problem for SLP-compressed words.	Inf. Process. Lett.	2004	DBLP DOI BibTeX RDF
25	Harry G. Mairson	Linear lambda calculus and PTIME-completeness.	J. Funct. Program.	2004	DBLP DOI BibTeX RDF
25	Manolis Koubarakis, Spiros Skiadopoulos	Querying temporal and spatial constraint networks in PTIME.	Artif. Intell.	2000	DBLP DOI BibTeX RDF
25	Martin Otto 0001	Bisimulation-invariant PTIME and higher-dimensional µ-calculus.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
25	Neil D. Jones	LOGSPACE and PTIME Characterized by Programming Languages.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
25	Patrick Doherty 0001, Witold Lukaszewicz, Andrzej Szalas	Declarative PTIME Queries for Relational Databases using Quantifier Elimination.	J. Log. Comput.	1999	DBLP DOI BibTeX RDF
25	Manolis Koubarakis, Spiros Skiadopoulos	Querying Temporal Constraint Networks in PTIME.	AAAI/IAAI	1999	DBLP BibTeX RDF
25	Fosca Giannotti, Dino Pedreschi	Datalog with Non-Deterministic Choice Computers NDB-PTIME.	J. Log. Program.	1998	DBLP DOI BibTeX RDF
25	Christine Ann Haught, Theodore A. Slaman	Automorphisms in the PTIME-Turing Degrees of Recursive Sets.	Ann. Pure Appl. Log.	1997	DBLP DOI BibTeX RDF
25	Martin Otto 0001	Capturing Bisimulation-Invariant Ptime.	LFCS	1997	DBLP DOI BibTeX RDF
25	Lauri Hella	Logical Hierarchies in PTIME.	Inf. Comput.	1996	DBLP DOI BibTeX RDF
25	Martin Otto 0001	Ptime Canonization for Two Variables with Counting	LICS	1995	DBLP DOI BibTeX RDF
25	Alexei P. Stolboushkin, Michael A. Taitslin	Is First Order Contained in an Initial Segment of PTIME?	CSL	1994	DBLP DOI BibTeX RDF
25	Lauri Hella	Logical Hierarchies in PTIME	LICS	1992	DBLP DOI BibTeX RDF
25	Juichi Shinoda, Theodore A. Slaman	On the Theory of the PTIME Degrees of the Recursive Sets.	J. Comput. Syst. Sci.	1990	DBLP DOI BibTeX RDF
25	Pratul Dublish, S. N. Maheshwari	Query Languages which Express all PTIME Queries for Trees and Unicyclic Graphs.	MFCS	1990	DBLP DOI BibTeX RDF
25	Juichi Shinoda, Theodore A. Slaman	On the theory of the PTIME degrees of the recursive sets.	SCT	1988	DBLP DOI BibTeX RDF
13	Nilesh N. Dalvi, Karl Schnaitter, Dan Suciu	Computing query probability with incidence algebras.	PODS	2010	DBLP DOI BibTeX RDF	incidence algebra, mobius inversion, probabilistic database
13	Nobutaka Suzuki, Yuji Fukushima	Satisfiability of simple xpath fragments in the presence of dtds.	WIDM	2009	DBLP DOI BibTeX RDF	satisfiability, xpath, xml, dtd
13	Xiang Zhou	CFI Construction and Balanced Graphs.	FAW	2009	DBLP DOI BibTeX RDF
13	Dario Colazzo, Giorgio Ghelli, Carlo Sartiani	Efficient asymmetric inclusion between regular expression types.	ICDT	2009	DBLP DOI BibTeX RDF	language inclusion, XML, regular expressions
13	Daniel Deutch, Tova Milo	TOP-K projection queries for probabilistic business processes.	ICDT	2009	DBLP DOI BibTeX RDF
13	Marcin Jurdzinski, Marta Z. Kwiatkowska, Gethin Norman, Ashutosh Trivedi 0001	Concavely-Priced Probabilistic Timed Automata.	CONCUR	2009	DBLP DOI BibTeX RDF
13	Phiniki Stouppa, Thomas Studer	Data Privacy for Knowledge Bases.	LFCS	2009	DBLP DOI BibTeX RDF
13	Byron Choi, Gao Cong, Wenfei Fan, Stratis Viglas	Updating Recursive XML Views of Relations.	J. Comput. Sci. Technol.	2008	DBLP DOI BibTeX RDF	XML, view update, XML views, XML publishing
13	Wenfei Fan, Floris Geerts, Xibei Jia, Anastasios Kementsietsidis	Conditional functional dependencies for capturing data inconsistencies.	ACM Trans. Database Syst.	2008	DBLP DOI BibTeX RDF	SQL, functional dependency, Data cleaning
13	Haiming Chen, Lei Chen	Inclusion Test Algorithms for One-Unambiguous Regular Expressions.	ICTAC	2008	DBLP DOI BibTeX RDF	One-unambiguous regular expression, algorithm, inclusion
13	Jianfeng Du, Yi-Dong Shen	Computing minimum cost diagnoses to repair populated DL-based ontologies.	WWW	2008	DBLP DOI BibTeX RDF	ontologies, diagnosis, description logics, disjunctive datalog