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 |