Stem tractabl$ (all stems)

81 papers:

ICALP-v1-2015-Cao #editing #parametricity

Unit Interval Editing is Fixed-Parameter Tractable (YC), pp. 306–317.

POPL-2015-BouajjaniEEH #concurrent #refinement

Tractable Refinement Checking for Concurrent Objects (AB, ME, CE, JH), pp. 651–662.

PODS-2014-Barcelo0V #evaluation #query #question

Does query evaluation tractability help query containment? (PB, MR, MYV), pp. 188–199.

PODS-2014-GrecoS #hybrid #query

Counting solutions to conjunctive queries: structural and hybrid tractability (GG, FS), pp. 132–143.

STOC-2014-CyganLPPS #parametricity

Minimum bisection is fixed parameter tractable (MC, DL, MP, MP, SS), pp. 323–332.

ICML-c1-2014-UriaML

A Deep and Tractable Density Estimator (BU, IM, HL), pp. 467–475.

LICS-CSL-2014-Chen #first-order #query #set

The tractability frontier of graph-like first-order query sets (HC), p. 9.

SAT-2014-HaanS #parametricity #reduction #satisfiability

Fixed-Parameter Tractable Reductions to SAT (RdH, SS), pp. 85–102.

PODS-2013-Wijsen #query

Charting the tractability frontier of certain conjunctive query answering (JW), pp. 189–200.

VLDB-2013-FanGN #big data #preprocessor #query

Making Queries Tractable on Big Data with Preprocessing (WF, FG, FN), pp. 685–696.

CADE-2013-Comon-LundhCS #deduction

Tractable Inference Systems: An Extension with a Deducibility Predicate (HCL, VC, GS), pp. 91–108.

CSL-2013-Goller #concurrent #model checking #parametricity

The Fixed-Parameter Tractability of Model Checking Concurrent Systems (SG), pp. 332–347.

VLDB-2012-CautisK #complexity #probability #query #using #xml

Answering Queries using Views over Probabilistic XML: Complexity and Tractability (BC, EK), pp. 1148–1159.

ICALP-v1-2012-ChitnisCHM #feedback #parametricity #set

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable (RHC, MC, MTH, DM), pp. 230–241.

ICALP-v1-2012-KratschPPW #graph #multi #parametricity

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs (SK, MP, MP, MW), pp. 581–593.

ICALP-v1-2012-LokshtanovR #constraints #multi

Parameterized Tractability of Multiway Cut with Parity Constraints (DL, MSR), pp. 750–761.

SAT-2012-CrowstonGJRSY #parametricity

Fixed-Parameter Tractability of Satisfying beyond the Number of Variables (RC, GG, MJ, VR, SS, AY), pp. 355–368.

STOC-2011-GroheKMW #parametricity

Finding topological subgraphs is fixed-parameter tractable (MG, KiK, DM, PW), pp. 479–488.

STOC-2011-MarxR #multi #parametricity

Fixed-parameter tractability of multicut parameterized by the size of the cutset (DM, IR), pp. 469–478.

DLT-J-2009-BertoniCR11 #context-free grammar #problem

The Inclusion Problem of Context-Free Languages: Some Tractable Cases (AB, CC, RR), pp. 289–299.

ICALP-v1-2011-CyganPPW #feedback #parametricity #set

Subset Feedback Vertex Set Is Fixed-Parameter Tractable (MC, MP, MP, JOW), pp. 449–461.

CIKM-2011-ChirkovaLR #xml

Tractable XML data exchange via relations (RC, LL, JLR), pp. 1629–1638.

ECMFA-2011-GogollaV #model transformation #testing

Tractable Model Transformation Testing (MG, AV), pp. 221–235.

SAT-2011-PetkeJ #csp #encoding #order #satisfiability

The Order Encoding: From Tractable CSP to Tractable SAT (JP, PJ), pp. 371–372.

PODS-2010-GrecoS #algorithm #consistency #power of

The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability (GG, FS), pp. 327–338.

PODS-2010-MartensNS #complexity #design #repository #xml

Schema design for XML repositories: complexity and tractability (WM, MN, TS), pp. 239–250.

STOC-2010-Marx #constraints #query

Tractable hypergraph properties for constraint satisfaction and conjunctive queries (DM), pp. 735–744.

KR-2010-DvorakPW #algorithm #parametricity #towards

Towards Fixed-Parameter Tractable Algorithms for Argumentation (WD, RP, SW).

KR-2010-PichlerRSW #bound #constraints #programming

Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth Is not Enough (RP, SR, SS, SW).

IJCAR-2010-MagkaKH #data type #logic

Tractable Extensions of the Description Logic EL with Numerical Datatypes (DM, YK, IH), pp. 61–75.

PODS-2009-CaliGL #framework #ontology #query

A general datalog-based framework for tractable query answering over ontologies (AC, GG, TL), pp. 77–86.

PODS-2009-Marnette #termination

Generalized schema-mappings: from termination to tractability (BM), pp. 13–22.

DLT-2009-BertoniCR #context-free grammar #problem

The Inclusion Problem of Context-Free Languages: Some Tractable Cases (AB, CC, RR), pp. 103–112.

ICALP-v1-2009-FellowsFLLRS #parametricity

Distortion Is Fixed Parameter Tractable (MRF, FVF, DL, EL, FAR, SS), pp. 463–474.

ICALP-v2-2009-GottlobGS #optimisation #problem #strict

Tractable Optimization Problems through Hypergraph-Based Structural Restrictions (GG, GG, FS), pp. 16–30.

ICML-2009-AdamsMM #parametricity #process

Tractable nonparametric Bayesian inference in Poisson processes with Gaussian process intensities (RPA, IM, DJCM), pp. 9–16.

SAC-2009-DrumwrightS #robust #simulation

A robust and tractable contact model for dynamic robotic simulation (ED, DAS), pp. 1176–1180.

ICALP-A-2008-RazgonO #parametricity #satisfiability

Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract) (IR, BO), pp. 551–562.

ICALP-B-2008-BjorklundM #automaton #nondeterminism

The Tractability Frontier for NFA Minimization (HB, WM), pp. 27–38.

SAC-2008-BartakC #network #recognition

Nested temporal networks with alternatives: recognition and tractability (RB, OC), pp. 156–157.

LICS-2008-Kahlon #abstraction #analysis #approach #concurrent #data flow #source code

Parameterization as Abstraction: A Tractable Approach to the Dataflow Analysis of Concurrent Programs (VK), pp. 181–192.

PODS-2007-GottlobMS #np-hard

Generalized hypertree decompositions: np-hardness and tractable variants (GG, ZM, TS), pp. 13–22.

ICALP-2007-FellowsFHV #graph

Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs (MRF, GF, DH, SV), pp. 340–351.

CSL-2007-ChenF #parametricity

Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping (YC, JF), pp. 389–404.

LICS-2007-IdziakMMVW #algebra

Tractability and learnability arising from algebras with few subpowers (PMI, PM, RM, MV, RW), pp. 213–224.

PODS-2006-GottlobPW #bound #database #design

Tractable database design through bounded treewidth (GG, RP, FW), pp. 124–133.

ICALP-v1-2006-BlellochDHRSS #parametricity #re-engineering

Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction (GEB, KD, EH, RR, RS, SS), pp. 667–678.

LICS-2006-KissV #congruence #on the

On Tractability and Congruence Distributivity (EWK, MV), pp. 221–230.

SIGIR-2005-Chai #empirical

Expectation of f-measures: tractable exact computation and some empirical observations of its properties (KMAC), pp. 593–594.

SAT-J-2004-ChenD05 #algebra #quantifier

Looking Algebraically at Tractable Quantified Boolean Formulas (HC, VD), pp. 71–79.

CSL-2005-ChenD #algorithm #consistency #constraints #game studies #quantifier

From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction (HC, VD), pp. 232–247.

LICS-2005-Dalmau

Generalized Majority-Minority Operations are Tractable (VD), pp. 438–447.

PODS-2004-MartensN #xml

Frontiers of Tractability for Typechecking Simple XML Transformations (WM, FN), pp. 23–34.

ICALP-2004-FlumGW #bound #nondeterminism #parametricity

Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits (JF, MG, MW), pp. 555–567.

ICML-2004-GoldenbergM #learning #scalability

Tractable learning of large Bayes net structures from sparse data (AG, AWM).

SAT-2004-ChenD #algebra #quantifier

Looking Algebraically at Tractable Quantified Boolean Formulas (HC, VD), pp. 224–229.

ICML-2003-CerquidesM #learning #modelling #naive bayes

Tractable Bayesian Learning of Tree Augmented Naive Bayes Models (JC, RLdM), pp. 75–82.

LICS-2003-Bulatov #constraints #problem

Tractable conservative Constraint Satisfaction Problems (AAB), p. 321–?.

SAT-2003-Szeider #on the #parametricity #satisfiability

On Fixed-Parameter Tractable Parameterizations of SAT (SS), pp. 188–202.

ICALP-2002-AdsulS #linear #logic

Complete and Tractable Local Linear Time Temporal Logics over Traces (BA, MAS), pp. 926–937.

STOC-2001-GroheSS #evaluation #query #question

When is the evaluation of conjunctive queries tractable? (MG, TS, LS), pp. 657–666.

CL-2000-AltamiranoE

Finding Tractable Formulas in NNF (EA, GEI), pp. 493–507.

PODS-1999-GottlobLS #query

Hypertree Decompositions and Tractable Queries (GG, NL, FS), pp. 21–32.

ICML-1999-LangleyS #analysis #classification #naive bayes

Tractable Average-Case Analysis of Naive Bayesian Classifiers (PL, SS), pp. 220–228.

CADE-1999-DemriG #first-order #logic

Tractable Transformations from Modal Provability Logics into First-Order Logic (SD, RG), pp. 16–30.

SIGIR-1997-GreiffCT #modelling #probability

Computationally Tractable Probabilistic Modeling of Boolean Operators (WRG, WBC, HRT), pp. 119–128.

SAS-1996-RehofM #constraints #finite

Tractable Constraints in Finite Semilattices (JR, TÆM), pp. 285–300.

KR-1996-JonssonDB #algebra #classification #subclass

Tractable Subclasses of the Point-Interval Algebra: A Complete Classification (PJ, TD, CB), pp. 352–363.

KR-1994-EtzioniGW #reasoning

Tractable Closed World Reasoning with Updates (OE, KG, DSW), pp. 178–189.

KR-1994-Selman

Near-Optimal Plans, Tractability, and Reactivity (BS), pp. 521–529.

KR-1994-Val #compilation #database #how

Tractable Databases: How to Make Propositional Unit Resolution Complete Through Compilation (AdV), pp. 551–561.

ILPS-1994-YouC #semantics

Tractable Argumentation Semantics via Iterative Belief Revision (JHY, RC), pp. 239–253.

PODS-1993-GrumbachM #algebra #towards

Towards Tractable Algebras for Bags (SG, TM), pp. 49–58.

ESEC-1993-CheungK #analysis #detection #distributed #source code

Tractable Flow Analysis for Anomaly Detection in Distributed Programs (SCC, JK), pp. 283–300.

KR-1992-Backstrom #equivalence

Equivalence and Tractability Results for SAS+ Planning (CB), pp. 126–137.

KR-1992-Dalal #deduction #information management #representation

Tractable Deduction in Knowledge Representation Systems (MD), pp. 393–402.

PODS-1991-GrumbachV #database #query

Tractable Query Languages for Complex Object Databases (SG, VV), pp. 315–327.

KR-1991-Bylander #abduction #functional #problem

The Monotonic Abduction Problem: A Functional Characterization on the Edge of Tractability (TB), pp. 70–77.

KR-1991-Witteveen #maintenance

Skeptical Reason Maintenance is Tractable (CW), pp. 570–581.

KR-1989-Etzioni

Tractable Decision-Analytic Control (OE), pp. 114–125.

ML-1988-MahadevanT #learning #on the

On the Tractability of Learning from Incomplete Theories (SM, PT), pp. 235–241.