BibSLEIGH
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
decidability
Google decidability

Tag #decidability

329 papers:

POPLPOPL-2020-HuL
Undecidability of d<: and its decidable fragments (JZSH, OL), p. 30.
POPLPOPL-2020-MackayPAG #dependent type #type system
Decidable subtyping for path dependent types (JM, AP, JA, LG), p. 27.
POPLPOPL-2020-MigeedP #question #what
What is decidable about gradual types? (ZM, JP), p. 29.
CSLCSL-2020-Mascle0 #modelling #satisfiability
The Keys to Decidable HyperLTL Satisfiability: Small Models or Very Simple Formulas (CM, MZ0), p. 16.
POPLPOPL-2019-MathurMV #source code #verification
Decidable verification of uninterpreted programs (UM, PM, MV0), p. 29.
CAVCAV-2019-BerkovitsLLPS #algorithm #composition #distributed #logic #verification
Verification of Threshold-Based Distributed Algorithms by Decomposition to Decidable Logics (IB, ML, GL, OP, SS), pp. 245–266.
CAVCAV-2019-FrohnG #integer #termination
Termination of Triangular Integer Loops is Decidable (FF, JG), pp. 426–444.
VMCAIVMCAI-2019-QiuW #logic #metric
A Decidable Logic for Tree Data-Structures with Measurements (XQ, YW), pp. 318–341.
DLTDLT-2018-Beier0 #automaton #finite
Decidability of Right One-Way Jumping Finite Automata (SB, MH0), pp. 109–120.
PLDIPLDI-2018-TaubeLMPSSWW #composition #deduction #distributed #verification
Modularity for decidability of deductive verification with applications to distributed systems (MT, GL, KLM, OP, MS, SS, JRW, DW), pp. 662–677.
POPLPOPL-2018-0001OV #type system
Decidability of conversion for type theory in type theory (AA0, , AV), p. 29.
POPLPOPL-2018-ChenCHLW #constraints #string #what
What is decidable about string constraints with the ReplaceAll function (TC, YC, MH, AWL, ZW), p. 29.
SASSAS-2018-McMillanP #deduction #verification
Deductive Verification in Decidable Fragments with Ivy (KLM, OP), pp. 43–55.
SASSAS-2018-Shoham #distributed #interactive #logic #protocol #using #verification
Interactive Verification of Distributed Protocols Using Decidable Logic (SS), pp. 77–85.
CSLCSL-2018-MadhusudanMS0 #higher-order #logic #synthesis
A Decidable Fragment of Second Order Logic With Applications to Synthesis (PM, UM, SS, MV0), p. 19.
DLTDLT-2017-Beier0K #automaton #complexity #finite
Operational State Complexity and Decidability of Jumping Finite Automata (SB, MH0, MK), pp. 96–108.
DLTDLT-2017-IbarraM #automaton #stack
Variations of Checking Stack Automata: Obtaining Unexpected Decidability Properties (OHI, IM), pp. 235–246.
DLTDLT-2017-Skrzypczak #complexity #logic
Connecting Decidability and Complexity for MSO Logic (MS), pp. 75–79.
ICFP-2017-Hamana #algebra #calculus #higher-order #how
How to prove your calculus is decidable: practical applications of second-order algebraic theories and computation (MH), p. 28.
OOPSLAOOPSLA-2017-PadonLSS #distributed #protocol #reasoning
Paxos made EPR: decidable reasoning about distributed protocols (OP, GL, MS, SS), p. 31.
LOPSTRLOPSTR-2017-GutierrezM #algebra #satisfiability
Variant-Based Decidable Satisfiability in Initial Algebras with Predicates (RG, JM), pp. 306–322.
CADECADE-2017-TeuckeW #constraints #first-order #linear #monad
Decidability of the Monadic Shallow Linear First-Order Fragment with Straight Dismatching Constraints (AT, CW), pp. 202–219.
CAVCAV-2017-LeT0C #induction #logic
A Decidable Fragment in Separation Logic with Inductive Predicates and Arithmetic (QLL, MT, JS0, WNC), pp. 495–517.
CSLCSL-2017-Boudou #logic
Decidable Logics with Associative Binary Modalities (JB), p. 15.
CSLCSL-2017-BoudouDF #logic
A Decidable Intuitionistic Temporal Logic (JB, MD, DFD), p. 17.
POPLPOPL-2016-PadonISKS #induction #invariant
Decidability of inferring inductive invariants (OP, NI, SS, AK, MS), pp. 217–231.
CSLCSL-2016-KolodziejczykMP #automaton #logic #theorem
The Logical Strength of Büchi's Decidability Theorem (LAK, HM, PP, MS), p. 16.
CIAACIAA-J-2013-KutribMMPW15 #automaton #finite #queue
Deterministic input-driven queue automata: Finite turns, decidability, and closure properties (MK, AM, CM, BP, MW), pp. 58–71.
CIAACIAA-2015-Prusa #context-free grammar #multi #problem
(Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars (DP), pp. 250–262.
DLTDLT-2015-AlmeidaBKK #on the
On Decidability of Intermediate Levels of Concatenation Hierarchies (JA, JB, OK, MK), pp. 58–70.
LATALATA-2015-AnselmoGM #2d
Structure and Measure of a Decidable Class of Two-dimensional Codes (MA, DG, MM), pp. 315–327.
LATALATA-2015-KrishnaMT #automaton #bound #problem #reachability #recursion
Time-Bounded Reachability Problem for Recursive Timed Automata is Undecidable (SNK, LM, AT), pp. 237–248.
FoSSaCSFoSSaCS-2015-ChadhaSVB #automaton #probability
Decidable and Expressive Classes of Probabilistic Automata (RC, APS, MV, YB), pp. 200–214.
FoSSaCSFoSSaCS-2015-Cotton-BarrattH #automaton #memory management #ml
Fragments of ML Decidable by Nested Data Class Memory Automata (CCB, DH, ASM, CHLO), pp. 249–263.
FoSSaCSFoSSaCS-2015-Velner #game studies #multi #robust
Robust Multidimensional Mean-Payoff Games are Undecidable (YV), pp. 312–327.
CADECADE-2015-Passmore #algebra #integer
Decidability of Univariate Real Algebra with Predicates for Rational and Integer Powers (GOP), pp. 181–196.
CSLCSL-2015-KuskeLM #infinity #monad #word
Infinite and Bi-infinite Words with Decidable Monadic Theories (DK, JL, AM), pp. 472–486.
LICSLICS-2015-BenediktCB #fixpoint #logic
Interpolation with Decidable Fixpoint Logics (MB, BtC, MVB), pp. 378–389.
LICSLICS-2015-GogaczM #query
The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable (TG, JM), pp. 281–292.
DLTDLT-J-2013-AnselmoGM14 #2d
Prefix Picture codes: a Decidable class of Two-Dimensional codes (MA, DG, MM), pp. 1017–1032.
DLTDLT-J-2013-BertoniCD14 #automaton #context-free grammar #on the #problem #quantum
On the Decidability of the Intersection Problem for Quantum Automata and Context-Free Languages (AB, CC, FD), pp. 1065–1082.
ICALPICALP-v2-2014-BojanczykGMS #infinity #on the
On the Decidability of MSO+U on Infinite Trees (MB, TG, HM, MS), pp. 50–61.
ICALPICALP-v2-2014-GogaczM #termination
All-Instances Termination of Chase is Undecidable (TG, JM), pp. 293–304.
ICALPICALP-v2-2014-OuaknineW14a #linear #sequence
Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences (JO, JW), pp. 330–341.
FMFM-2014-SanatiMM #guidelines #logic #metric #using
Analyzing Clinical Practice Guidelines Using a Decidable Metric Interval-Based Temporal Logic (MYS, WM, TSEM), pp. 611–626.
RTARTA-TLCA-2014-CarvalhoS #polynomial #set
An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting (DdC, JGS), pp. 179–193.
KRKR-2014-BorgwardtDP #logic
Decidable Gödel Description Logics without the Finitely-Valued Model Property (SB, FD, RP).
KRKR-2014-LakemeyerL #calculus #reasoning
Decidable Reasoning in a Fragment of the Epistemic Situation Calculus (GL, HJL).
LICSLICS-CSL-2014-BaierKKW #complexity #linear #logic #monitoring
Weight monitoring with linear temporal logic: complexity and decidability (CB, JK, SK, SW), p. 10.
LICSLICS-CSL-2014-CharatonikKM #logic #transitive
Decidability of weak logics with deterministic transitive closure (WC, EK, FM), p. 10.
LICSLICS-CSL-2014-Ilik #axiom #morphism
Axioms and decidability for type isomorphism in the presence of sums (DI), p. 7.
CIAACIAA-2013-KutribMMPW #automaton #finite #queue
Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties (MK, AM, CM, BP, MW), pp. 232–243.
CIAACIAA-2013-MrazO #automaton
λ-Confluence Is Undecidable for Clearing Restarting Automata (FM, FO), pp. 256–267.
DLTDLT-2013-BertoniCD #automaton #context-free grammar #finite #linear #problem #quantum
Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem (AB, CC, FD), pp. 82–93.
LATALATA-2013-DelzannoT #complexity #network #verification
Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks (GD, RT), pp. 238–249.
RTARTA-2013-FujitaS
Decidable structures between Church-style and Curry-style (KeF, AS), pp. 190–205.
RTARTA-2013-TushkanovaRGK #automation #calculus
Automatic Decidability: A Schematic Calculus for Theories with Counting Operators (ET, CR, AG, OK), pp. 303–318.
PPDPPPDP-2013-CalauttiGT #detection #logic programming #source code
Detecting decidable classes of finitely ground logic programs with function symbols (MC, SG, IT), pp. 239–250.
CADECADE-2013-KersaniP #first-order
Completeness and Decidability Results for First-Order Clauses with Indices (AK, NP), pp. 58–75.
CSLCSL-2013-ChatterjeeCT #markov #process #what
What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives (KC, MC, MT), pp. 165–180.
CSLCSL-2013-WangB #equation #semantics #type system
Semantics of Intensional Type Theory extended with Decidable Equational Theories (QW, BB), pp. 653–667.
ICLPICLP-J-2013-GottlobMP #paradigm
Combining decidability paradigms for existential rules (GG, MM, AP), pp. 877–892.
LICSLICS-2013-HofmanMT #simulation
Decidability of Weak Simulation on One-Counter Nets (PH, RM, PT), pp. 203–212.
DLTDLT-J-2011-CharlierRS12 #automation #sequence
Enumeration and Decidable Properties of Automatic Sequences (EC, NR, JS), pp. 1035–1066.
DLTDLT-2012-BealCDJL #geometry #regular expression
Decidability of Geometricity of Regular Languages (MPB, JMC, JPD, HJ, SL), pp. 62–72.
RTARTA-2012-BertrandDKSS #graph transformation #on the #reachability
On the Decidability Status of Reachability and Coverability in Graph Transformation Systems (NB, GD, BK, AS, JS), pp. 101–116.
ICGTICGT-2012-AotoK #confluence #term rewriting
Rational Term Rewriting Revisited: Decidability and Confluence (TA, JK), pp. 172–186.
KRKR-2012-GiacomoLP #bound #calculus #verification
Bounded Situation Calculus Action Theories and Decidable Verification (GDG, YL, FP).
SEKESEKE-2012-LuZZBA #invariant #petri net
Decidability of Minimal Supports of S-invariants and the Computation of their Supported S-invariants of Petri Nets (FL, QZ, HZ, YB, JA), pp. 340–345.
ESOPESOP-2012-AtigBBM #memory management #modelling #question #what
What’s Decidable about Weak Memory Models? (MFA, AB, SB, MM), pp. 26–46.
CAVCAV-2012-GuhaNA #automaton #bisimulation #on the
On Decidability of Prebisimulation for Timed Automata (SG, CN, SAK), pp. 444–461.
CSLCSL-2012-KufleitnerW
The FO2 alternation hierarchy is decidable (MK, PW), pp. 426–439.
CSLCSL-2012-KuusistoMV #first-order #geometry
Undecidable First-Order Theories of Affine Geometries (AK, JM, JV), pp. 470–484.
ICLPICLP-J-2012-AlvianoFLM #complexity #datalog #quantifier #semantics
Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues (MA, WF, NL, MM), pp. 701–718.
IJCARIJCAR-2012-FontaineMW
Combination of Disjoint Theories: Beyond Decidability (PF, SM, CW), pp. 256–270.
LICSLICS-2012-ChatterjeeT #automaton #infinity #probability #problem #word
Decidable Problems for Probabilistic Automata on Infinite Words (KC, MT), pp. 185–194.
LICSLICS-2012-Jancar #equivalence #first-order
Decidability of DPDA Language Equivalence via First-Order Grammars (PJ), pp. 415–424.
LICSLICS-2012-MichaliszynO #logic
Decidable Elementary Modal Logics (JM, JO), pp. 491–500.
DLTDLT-2011-CharlierRS #automation #sequence
Enumeration and Decidable Properties of Automatic Sequences (EC, NR, JS), pp. 165–179.
ICALPICALP-v2-2011-HopkinsMO #automaton #ml
A Fragment of ML Decidable by Visibly Pushdown Automata (DH, ASM, CHLO), pp. 149–161.
GT-VMTGT-VMT-2011-BrugginkH #graph
Decidability and Expressiveness of Finitely Representable Recognizable Graph Languages (HJSB, MH).
POPLPOPL-2011-MadhusudanPQ #logic
Decidable logics combining heap structures and data (PM, GP, XQ), pp. 611–622.
CSLCSL-2011-CantoneLA #logic #order #quantifier #set
A Decidable Quantified Fragment of Set Theory Involving Ordered Pairs with Applications to Description Logics (DC, CL, MNA), pp. 129–143.
CSLCSL-2011-Kieronski #linear #logic #order
Decidability Issues for Two-Variable Logics with Several Linear Orders (EK), pp. 337–351.
LICSLICS-2011-BarrasJSW #first-order #higher-order #named #type system
CoQMTU: A Higher-Order Type Theory with a Predicative Hierarchy of Universes Parametrized by a Decidable First-Order Theory (BB, JPJ, PYS, QW), pp. 143–151.
LICSLICS-2011-BodirskyPT
Decidability of Definability (MB, MP, TT), pp. 321–328.
LICSLICS-2011-BresolinMSS #logic #what
What’s Decidable about Halpern and Shoham’s Interval Logic? The Maximal Fragment ABBL (DB, AM, PS, GS), pp. 387–396.
LICSLICS-2011-Figueira #logic #word
A Decidable Two-Way Logic on Data Words (DF), pp. 365–374.
ICALPICALP-v2-2010-GimbertO #automaton #finite #probability #problem #word
Probabilistic Automata on Finite Words: Decidable and Undecidable Problems (HG, YO), pp. 527–538.
ICALPICALP-v2-2010-MarcinkowskiMK #logic
B and D Are Enough to Make the Halpern-Shoham Logic Undecidable (JM, JM, EK), pp. 357–368.
ICALPICALP-v2-2010-MontanariPS #logic
Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals (AM, GP, PS), pp. 345–356.
GT-VMTGT-VMT-2010-RehakSSH
Decidable Race Condition and Open Coregions in HMSC (VR, PS, JS, LH).
ICPRICPR-2010-LobranoTGR
A Score Decidability Index for Dynamic Score Combination (CL, RT, GG, FR), pp. 69–72.
KRKR-2010-BagetLM
Walking the Decidability Line for Rules with Existential Variables (JFB, ML, MLM).
KRKR-2010-BartholomewL #modelling
A Decidable Class of Groundable Formulas in the General Theory of Stable Models (MB, JL).
KRKR-2010-CeramiEB #logic
Decidability of a Description Logic over Infinite-Valued Product Logic (MC, FE, FB).
KRKR-2010-GlimmR #query
Status QIO: Conjunctive Query Entailment Is Decidable (BG, SR).
FoSSaCSFoSSaCS-2010-DemriS #ltl #model checking
When Model-Checking Freeze LTL over Counter Machines Becomes Decidable (SD, AS), pp. 176–190.
FoSSaCSFoSSaCS-2010-Stirling #higher-order
Introduction to Decidability of Higher-Order Matching (CS), p. 1.
FoSSaCSFoSSaCS-2010-ToL #algorithm #infinity #ltl #model checking
Algorithmic Metatheorems for Decidable LTL Model Checking over Infinite Systems (AWT, LL), pp. 221–236.
STOCSTOC-2010-GodoyGRA #problem
The HOM problem is decidable (GG, OG, LR, ), pp. 485–494.
ICLPICLP-J-2010-AlvianoFL #effectiveness #query
Disjunctive ASP with functions: Decidable queries and effective computation (MA, WF, NL), pp. 497–512.
ICLPICLP-J-2010-BaseliceB #source code #subclass
A decidable subclass of finitary programs (SB, PAB), pp. 481–496.
ICLPICLP-J-2010-GabbrielliMMS
Decidability properties for fragments of CHR (MG, JM, MCM, JS), pp. 611–626.
IJCARIJCAR-2010-AravantinosCP
A Decidable Class of Nested Iterated Schemata (VA, RC, NP), pp. 293–308.
DLTDLT-2009-Souza #equivalence #on the #transducer
On the Decidability of the Equivalence for a Certain Class of Transducers (RdS), pp. 478–489.
ICALPICALP-v1-2009-AubrunB #finite
Decidability of Conjugacy of Tree-Shifts of Finite Type (NA, MPB), pp. 132–143.
ICALPICALP-v2-2009-Michaliszyn #transitive
Decidability of the Guarded Fragment with the Transitive Closure (JM), pp. 261–272.
ICALPICALP-v2-2009-PlaceS
A Decidable Characterization of Locally Testable Tree Languages (TP, LS), pp. 285–296.
ICFPICFP-2009-SchrijversJSV #data type #type inference
Complete and decidable type inference for GADTs (TS, SLPJ, MS, DV), pp. 341–352.
STOCSTOC-2009-KawarabayashiR
Hadwiger’s conjecture is decidable (KiK, BAR), pp. 445–454.
CADECADE-2009-HorbachW
Decidability Results for Saturation-Based Model Building (MH, CW), pp. 404–420.
CSLCSL-2009-AtseriasW #consistency #constraints #problem
Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems (AA, MW), pp. 102–116.
CSLCSL-2009-DuparcFM #automaton #game studies #linear #problem
Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata (JD, AF, FM), pp. 225–239.
CSLCSL-2009-MontanariPS #logic
A Decidable Spatial Logic with Cone-Shaped Cardinal Directions (AM, GP, PS), pp. 394–408.
CSLCSL-2009-Rabinovich #problem
Decidable Extensions of Church’s Problem (AR), pp. 424–439.
ICLPICLP-2009-LierlerL #source code
One More Decidable Class of Finitely Ground Programs (YL, VL), pp. 489–493.
LICSLICS-2009-BertrandGG #game studies #probability
Qualitative Determinacy and Decidability of Stochastic Games with Signals (NB, BG, HG), pp. 319–328.
LICSLICS-2009-Kahlon #bound #communication #thread
Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of Pairwise CFL-Reachability for Threads Communicating via Locks (VK), pp. 27–36.
DLTDLT-2008-CsimaK #question #reachability
When Is Reachability Intrinsically Decidable? (BFC, BK), pp. 216–227.
DLTDLT-2008-DennunzioF #2d #automaton
Decidable Properties of 2D Cellular Automata (AD, EF), pp. 264–275.
DLTDLT-2008-Jancar #similarity
Selected Ideas Used for Decidability and Undecidability of Bisimilarity (PJ), pp. 56–71.
DLTDLT-2008-Souza #equivalence #on the #transducer
On the Decidability of the Equivalence for k-Valued Transducers (RdS), pp. 252–263.
RTARTA-2008-KojimaS #linear #reachability #term rewriting
Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems (YK, MS), pp. 187–201.
CAiSECAiSE-2008-QueraltT #constraints #reasoning #uml
Decidable Reasoning in UML Schemas with Constraints (AQ, ET), pp. 281–295.
FoSSaCSFoSSaCS-2008-GodoyMT #morphism
Classes of Tree Homomorphisms with Decidable Preservation of Regularity (GG, SM, ST), pp. 127–141.
FoSSaCSFoSSaCS-2008-HabermehlIV #array #integer #question #what
What Else Is Decidable about Integer Arrays? (PH, RI, TV), pp. 474–489.
CSLCSL-2008-Thomas #model transformation #monad #proving
Model Transformations in Decidability Proofs for Monadic Theories (WT), pp. 23–31.
LICSLICS-2008-LanesePSS #calculus #higher-order #on the #process
On the Expressiveness and Decidability of Higher-Order Process Calculi (IL, JAP, DS, AS), pp. 145–155.
RTARTA-2007-GodoyH #term rewriting
Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems (GG, EH), pp. 184–199.
PPDPPPDP-2007-LushmanC #problem
A larger decidable semiunification problem (BL, GVC), pp. 143–152.
CADECADE-2007-LynchT #automation #revisited
Automatic Decidability and Combinability Revisited (CL, DKT), pp. 328–344.
PODSPODS-2006-Rosati #database #finite #on the #query
On the decidability and finite controllability of query processing in databases with incomplete information (RR), pp. 356–365.
RTARTA-2006-WangS #linear #termination
Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems (YW, MS), pp. 343–356.
POPLPOPL-2006-Dam #proving
Decidability and proof systems for language-based noninterference relations (MD), pp. 67–78.
TACASTACAS-2006-OuaknineW #logic #metric #safety
Safety Metric Temporal Logic Is Fully Decidable (JO, JW), pp. 411–425.
CSLCSL-2006-RabinovichT
Decidable Theories of the Ordering of Natural Numbers with Unary Predicates (AMR, WT), pp. 562–574.
IJCARIJCAR-2006-BonacinaGNRZ
Decidability and Undecidability Results for Nelson-Oppen and Rewrite-Based Decision Procedures (MPB, SG, EN, SR, DZ), pp. 513–527.
VMCAIVMCAI-2006-BradleyMS #array #question #what
What’s Decidable About Arrays? (ARB, ZM, HBS), pp. 427–442.
DLTDLT-J-2004-Lohrey05 #automation #complexity #monad
Decidability and complexity in automatic monoids (ML), pp. 707–722.
ICALPICALP-2005-AbdullaDOW #automaton #complexity
Decidability and Complexity Results for Timed Automata via Channel Machines (PAA, JD, JO, JW), pp. 1089–1101.
ICALPICALP-2005-Laird
Decidability in Syntactic Control of Interference (JL), pp. 904–916.
TLCATLCA-2005-AehligMO #higher-order #monad #recursion
The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable (KA, JGdM, CHLO), pp. 39–54.
FoSSaCSFoSSaCS-2005-BozgaI #on the
On Decidability Within the Arithmetic of Addition and Divisibility (MB, RI), pp. 425–439.
FoSSaCSFoSSaCS-2005-Kaiser #confluence #term rewriting
Confluence of Right Ground Term Rewriting Systems Is Decidable (LK), pp. 470–489.
FoSSaCSFoSSaCS-2005-MurawskiW #algol #higher-order
Third-Order Idealized Algol with Iteration Is Decidable (ASM, IW), pp. 202–218.
CADECADE-2005-ZhangSM #first-order
The Decidability of the First-Order Theory of Knuth-Bendix Order (TZ, HBS, ZM), pp. 131–148.
CSLCSL-2005-Blanqui #algebra #calculus
Decidability of Type-Checking in the Calculus of Algebraic Constructions with Size Annotations (FB), pp. 135–150.
CSLCSL-2005-KhoussainovR #algebra
Decidability of Term Algebras Extending Partial Algebras (BK, SR), pp. 292–308.
CSLCSL-2005-Lutz
PDL with Intersection and Converse Is Decidable (CL), pp. 413–427.
LICSLICS-2005-KieronskiO #first-order #logic
Small Substructures and Decidability Issues for First-Order Logic with Two Variables (EK, MO), pp. 448–457.
LICSLICS-2005-OuaknineW #logic #metric #on the
On the Decidability of Metric Temporal Logic (JO, JW), pp. 188–197.
PODSPODS-2004-Bonatti #datalog #on the #query #recursion
On the Decidability of Containment of Recursive Datalog Queries — Preliminary report (PAB), pp. 297–306.
DLTDLT-2004-Lohrey #automation #complexity #monad
Decidability and Complexity in Automatic Monoids (ML), pp. 308–320.
SEFMSEFM-2004-LanotteMT #parametricity #probability #security
Decidability Results for Parametric Probabilistic Transition Systems with an Application to Security (RL, AMS, AT), pp. 114–121.
ESOPESOP-2004-DuckPSS #dependence #functional #type inference
Sound and Decidable Type Inference for Functional Dependencies (GJD, SLPJ, PJS, MS), pp. 49–63.
ESOPESOP-2004-Shmatikov #analysis #composition #encryption #protocol
Decidable Analysis of Cryptographic Protocols with Products and Modular Exponentiation (VS), pp. 355–369.
FoSSaCSFoSSaCS-2004-ConfortiG
Decidability of Freshness, Undecidability of Revelation (GC, GG), pp. 105–120.
TACASTACAS-2004-KrcalY #analysis #automaton #problem #scheduling #using
Decidable and Undecidable Problems in Schedulability Analysis Using Timed Automata (PK, WY), pp. 236–250.
CSLCSL-2004-ImmermanRRSY #bound #logic #transitive
The Boundary Between Decidability and Undecidability for Transitive-Closure Logics (NI, AMR, TWR, SS, GY), pp. 160–174.
IJCARIJCAR-2004-BaaderGT #logic #problem #word
A New Combination Procedure for the Word Problem That Generalizes Fusion Decidability Results in Modal Logics (FB, SG, CT), pp. 183–197.
LICSLICS-2004-OuaknineW #automaton #on the #problem
On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap (JO, JW), pp. 54–63.
PODSPODS-2003-CaliLR #complexity #consistency #database #on the #query #semistructured data
On the decidability and complexity of query answering over inconsistent and incomplete databases (AC, DL, RR), pp. 260–271.
RTARTA-2003-Comon-LundhC #encryption #first-order #logic #protocol
New Decidability Results for Fragments of First-Order Logic and Application to Cryptographic Protocols (HCL, VC), pp. 148–164.
RTARTA-2003-Verma #automaton #equation
Two-Way Equational Tree Automata for AC-Like Theories: Decidability and Closure Properties (KNV), pp. 180–196.
SASSAS-2003-KuncakR #abstraction
Existential Heap Abstraction Entailment Is Undecidable (VK, MCR), pp. 418–438.
FoSSaCSFoSSaCS-2003-BertrandS #model checking
Model Checking Lossy Channels Systems Is Probably Decidable (NB, PS), pp. 120–135.
TACASTACAS-2003-FontaineG #invariant #validation
Decidability of Invariant Validation for Paramaterized Systems (PF, EPG), pp. 97–112.
CADECADE-2003-Schmidt-Schauss #bound #higher-order
Decidability of Arity-Bounded Higher-Order Matching (MSS), pp. 488–502.
ICLPICLP-2003-Valencia03a #concurrent #constraints #ltl #programming
Timed Concurrent Constraint Programming: Decidability Results and Their Application to LTL (FDV), pp. 422–437.
LICSLICS-2003-KuncakR #recursion #type system
Structural Subtyping of Non-Recursive Types is Decidable (VK, MCR), pp. 96–107.
LICSLICS-2003-OuaknineW #automaton #robust
Revisiting Digitization, Robustness, and Decidability for Timed Automata (JO, JW), pp. 198–207.
LICSLICS-2003-PitermanV #future of #stack
Micro-Macro Stack Systems: A New Frontier of Elementary Decidability for Sequential Systems (NP, MYV), p. 381–?.
ICALPICALP-2002-Colcombet #first-order #graph #on the #product line #reachability
On Families of Graphs Having a Decidable First Order Theory with Reachability (TC), pp. 98–109.
ICALPICALP-2002-Senizergues
L(A) = L(B)? Decidability Results from Complete Formal Systems (GS), p. 37.
RTARTA-2002-DoughertyW #higher-order
A Decidable Variant of Higher Order Matching (DJD, TW), pp. 340–351.
RTARTA-2002-OhsakiT #equation
Decidability and Closure Properties of Equational Tree Languages (HO, TT), pp. 114–128.
SASSAS-2002-Muller-OlmS #polynomial
Polynomial Constants Are Decidable (MMO, HS), pp. 4–19.
TACASTACAS-2002-FersmanPY #automaton #process #scheduling
Timed Automata with Asynchronous Processes: Schedulability and Decidability (EF, PP, WY), pp. 67–82.
CADECADE-2002-GeorgievaHS
A New Clausal Class Decidable by Hyperresolution (LG, UH, RAS), pp. 260–274.
CSLCSL-2002-BeauquierRS #logic #model checking #probability
A Logic of Probability with Decidable Model-Checking (DB, AMR, AS), pp. 306–321.
CSLCSL-2002-Schmidt-SchaussS #bound #higher-order #unification
Decidability of Bounded Higher-Order Unification (MSS, KUS), pp. 522–536.
LICSLICS-2002-HirschkoffLS #logic
Separability, Expressiveness, and Decidability in the Ambient Logic (DH, ÉL, DS), pp. 423–432.
LICSLICS-2002-HodkinsonWZ #branch #first-order #logic
Decidable and Undecidable Fragments of First-Order Branching Temporal Logics (IMH, FW, MZ), pp. 393–402.
LICSLICS-2002-LynchM #automation
Automatic Decidability (CL, BM), p. 7–?.
LICSLICS-2002-Ong #algol #equivalence
Observational Equivalence of 3rd-Order Idealized Algol is Decidable (CHLO), pp. 245–256.
SATSAT-2002-PorschenRS #satisfiability
X3SAT is decidable in time O(2n/5) (SP, BR, ES), p. 10.
ICALPICALP-2001-DiekertM #commutative #equation
Solvability of Equations in Free Partially Commutative Groups Is Decidable (VD, AM), pp. 543–554.
ICALPICALP-2001-Kunc #problem
The Trace Coding Problem Is Undecidable (MK), pp. 603–614.
ICALPICALP-2001-MargaraS #graph #network
Decidable Properties of Graphs of All-Optical Networks (LM, JS), pp. 518–529.
FoSSaCSFoSSaCS-2001-Stirling #parallel #process #set #similarity
Decidability of Weak Bisimilarity for a Subset of Basic Parallel Processes (CS), pp. 379–393.
STOCSTOC-2001-SchaeferS #graph #string
Decidability of string graphs (MS, DS), pp. 241–246.
CSLCSL-2001-BoerE #logic #navigation
Decidable Navigation Logics for Object Structures (FSdB, RMvE), pp. 324–338.
CSLCSL-2001-CharatonikT #mobile #model checking
The Decidability of Model Checking Mobile Ambients (WC, JMT), pp. 339–354.
IJCARIJCAR-2001-GieslK #induction #theorem
Decidable Classes of Inductive Theorems (JG, DK), pp. 469–484.
IJCARIJCAR-2001-LynchM #complexity #equation #linear
Decidability and Complexity of Finitely Closable Linear Equational Theories (CL, BM), pp. 499–513.
LICSLICS-2001-Ganzinger #concept #problem #semantics #word
Relating Semantic and Proof-Theoretic Concepts for Polynominal Time Decidability of Uniform Word Problems (HG), pp. 81–90.
ICALPICALP-2000-LugiezS #first-order #logic
Decidable First-Order Transition Logics for PA-Processes (DL, PS), pp. 342–353.
STOCSTOC-2000-MotwaniPSV #on the #problem
On the decidability of accessibility problems (RM, RP, VAS, SV), pp. 306–315.
ICLPCL-2000-LehmannL #calculus
Decidability Results for the Propositional Fluent Calculus (HL, ML), pp. 762–776.
ICLPCL-2000-NarendranR #formal method
The Theory of Total Unary RPO Is Decidable (PN, MR), pp. 660–672.
LICSLICS-2000-LindellW #finite #first-order
The Role of Decidability in First Order Separations over Classes of Finite Structures (SL, SW), pp. 45–50.
IWPCIWPC-1999-HarmanFHBD #approximate
Program Simplification as a Means of Approximating Undecidable Propositions (MH, CF, RMH, DB, SD), pp. 208–217.
DLTDLT-1999-AndreBC #bound #on the #query
On decidability of boundedness property for regular path queries (YA, FB, ACC), pp. 245–256.
DLTDLT-1999-FernauR
Decidability of code properties (HF, KR, LS), pp. 153–163.
ICALPICALP-1999-CortierGJV #reachability
Decidable Fragments of Simultaneous Rigid Reachability (VC, HG, FJ, MV), pp. 250–260.
ICALPICALP-1999-HirshfeldJ #algebra #bisimulation #process
Bisimulation Equivanlence Is Decidable for Normed Process Algebra (YH, MJ), pp. 412–421.
ICALPICALP-1999-HirshfeldR #framework #logic
A Framework for Decidable Metrical Logics (YH, AMR), pp. 422–432.
RTARTA-1999-LimetR
A New Result about the Decidability of the Existential One-Step Rewriting Theory (SL, PR), pp. 118–132.
RTARTA-1999-NagayaT #term rewriting
Decidability for Left-Linaer Growing Term Rewriting Systems (TN, YT), pp. 256–270.
POPLPOPL-1999-KfouryW #type inference
Principality and Decidable Type Inference for Finite-Rank Intersection Types (AJK, JBW), pp. 161–174.
ESOPESOP-1999-BenediktRS #data type #linked data #logic #open data
A Decidable Logic for Describing Linked Data Structures (MB, TWR, SS), pp. 2–19.
CADECADE-1999-Schmidt-SchaussS #equation
Solvability of Context Equations with Two Context Variables is Decidable (MSS, KUS), pp. 67–81.
CADECADE-1999-Sofronie-Stokkermans #complexity #on the
On the Universal Theory of Varieties of Distributive Lattices with Operators: Some Decidability and Complexity Results (VSS), pp. 157–171.
PODSPODS-1998-BaileyDR #database #problem #termination
Decidability and Undecidability Results for the Termination Problem of Active Database Rules (JB, GD, KR), pp. 264–273.
PODSPODS-1998-CalvaneseGL #constraints #on the #query
On the Decidability of Query Containment under Constraints (DC, GDG, ML), pp. 149–158.
ICALPICALP-1998-DufourdFS
Reset Nets Between Decidability and Undecidability (CD, AF, PS), pp. 103–115.
ICALPICALP-1998-Zakharov #approach #equivalence #performance #source code
An Efficient and Unified Approach to the Decidability of Equivalence of Propositional Programs (VAZ), pp. 247–258.
RTARTA-1998-DegtyarevGNVV
The Decidability of Simultaneous Rigid E-Unification with One Variable (AD, YG, PN, MV, AV), pp. 181–195.
RTARTA-1998-Genet #approximate #normalisation #set
Decidable Approximations of Sets of Descendants and Sets of Normal Forms (TG), pp. 151–165.
RTARTA-1998-Levy #higher-order #problem #unification
Decidable and Undecidable Second-Order Unification Problems (JL), pp. 47–60.
RTARTA-1998-Waldmann #normalisation
Normalization of S-Terms is Decidable (JW), pp. 138–150.
KRKR-1998-WolterZ #logic #on the
On the Decidability of Description Logics with Modal Operators (FW, MZ), pp. 512–523.
CSLCSL-1998-RicheM #complexity
Belnap, Urquhart and Relevant Decidability & Complexity. “Das ist nicht Mathematik, das ist Theologie.” (JR, RKM), pp. 224–240.
PODSPODS-1997-GuchtDGV #algebra #database #on the #set
On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases (FD, MG, LV, DVG), pp. 68–77.
DLTDLT-1997-MateescuSY #context-free grammar
Decidability of fairness for context-free languages (AM, KS, SY), pp. 351–364.
ICALPICALP-1997-Jancar #bisimulation #equivalence #process
Bisimulation Equivalence is Decidable for One-Counter Processes (PJ), pp. 549–559.
ICALPICALP-1997-NarendranO #confluence #finite #problem #string #term rewriting #word
The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent (PN, FO), pp. 638–648.
ICALPICALP-1997-Senizergues #automaton #equivalence #problem
The Equivalence Problem for Deterministic Pushdown Automata is Decidable (GS), pp. 671–681.
RTARTA-1997-OttoKK #monad #problem #word
Cross-Sections for Finitely Presented Monoids with Decidable Word Problems (FO, MK, YK), pp. 53–67.
RTARTA-1997-Vorobyov #first-order #linear
The First-Order Theory of One Step Rewriting in Linear Noetherian Systems is Undecidable (SGV), pp. 254–268.
TLCATLCA-1997-MalolepszyMZ
Schwichtenberg-Style λ Definability Is Undecidable (JM, MM, MZ), pp. 267–283.
STOCSTOC-1997-HerlihyR #distributed
The Decidability of Distributed Decision Tasks (MH, SR), pp. 589–598.
TAPSOFTTAPSOFT-1997-SeynhaeveTT #constraints #grid
Grid Structure and Undecidable Constraint Theories (FS, MT, RT), pp. 357–368.
CADECADE-1997-DurandM #call-by #term rewriting
Decidable Call by Need Computations in term Rewriting (ID, AM), pp. 4–18.
CAVCAV-1997-Fisler #diagrams #regular expression
Containing of Regular Languages in Non-Regular Timing Diagram Languages is Decidable (KF), pp. 155–166.
LICSLICS-1997-GradelOR #logic
Two-Variable Logic with Counting is Decidable (EG, MO, ER), pp. 306–317.
LICSLICS-1997-Vorobyov
The “Hardest” Natural Decidable Theory (SGV), pp. 294–305.
ICALPICALP-1996-BosscherG #process #scalability
Regularity for a Large Class of Context-Free Processes is Decidable (DJBB, WODG), pp. 182–193.
ICALPICALP-1996-Caucal #graph #infinity #monad #on the
On Infinite Transition Graphs Having a Decidable Monadic Theory (DC), pp. 194–205.
RTARTA-1996-Jacquemard #approximate #term rewriting
Decidable Approximations of Term Rewriting Systems (FJ), pp. 362–376.
RTARTA-1996-Treinen #first-order
The First-Order Theory of One-Step Rewriting is Undecidable (RT), pp. 276–286.
PPDPALP-1996-FassbenderM #recursion #strict
A Strict Border for the Decidability of E-Unification for Recursive Functions (HF, SM), pp. 194–208.
PPDPPLILP-1996-Ruggieri #logic programming #semantics #testing
Decidability of Logic Program Semantics and Applications to Testing (SR), pp. 347–362.
SASSAS-1996-RouxR #automaton #hybrid
Uniformity for the Decidability of Hybrid Automata (OFR, VR), pp. 301–316.
TAPSOFTTAPSOFT-J-1995-Salomaa96 #automaton #equivalence
Decidability of Equivalence for Deterministic Synchronized Tree Automata (KS), pp. 171–192.
CADECADE-1996-Weidenbach #pseudo #unification
Unification in Pseudo-Linear Sort Theories is Decidable (CW), pp. 343–357.
CSLCSL-1996-KozenS #algebra #testing
Kleene Algebra with Tests: Completeness and Decidability (DK, FS), pp. 244–259.
CSLCSL-1996-Setzer #induction
Inductive Definitions with Decidable Atomic Formulas (AS), pp. 414–430.
LICSLICS-1996-AbdullaCJT #infinity #theorem
General Decidability Theorems for Infinite-State Systems (PAA, KC, BJ, YKT), pp. 313–321.
LICSLICS-1996-DegtyarevV #logic #problem
Decidability Problems for the Prenex Fragment of Intuitionistic Logic (AD, AV), pp. 503–512.
LICSLICS-1996-Marcinkowski #bound #datalog
DATALOG SIRUPs Uniform Boundedness is Undecidable (JM), pp. 13–24.
LICSLICS-1996-Nieuwenhuis
Basic Paramodulation and Decidable Theories (RN), pp. 473–482.
LICSLICS-1996-TiurynU #higher-order #problem #type system
The Subtyping Problem for Second-Order Types is Undecidable (JT, PU), pp. 74–85.
DLTDLT-1995-Jedrzejowicz #problem
An Undecidable Problem for Shuffle Languages (JJ), pp. 112–118.
TLCATLCA-1995-KurataT #type system
Decidable Properties of Intersection Type Systems (TK, MT), pp. 297–311.
POPLPOPL-1995-CastagnaP #bound #named #quantifier
Corrigendum: Decidable Bounded Quantification (GC, BCP), p. 408.
POPLPOPL-1995-Vorobyov #bound #quantifier
Structural Decidable Extensions of Bounded Quantification (SGV), pp. 164–175.
STOCSTOC-1995-HenzingerKPV #automaton #hybrid #question #what
What’s decidable about hybrid automata? (TAH, PWK, AP, PV), pp. 373–382.
TAPSOFTTAPSOFT-1995-Salomaa #automaton #equivalence
Decidability of Equivalence for Deterministic Synchronized Tree Automata (KS), pp. 140–154.
LICSLICS-1995-Kopylov #linear #logic
Decidability of Linear Affine Logic (APK), pp. 496–504.
ICALPICALP-1994-AbdullaJ #problem #source code #verification
Undecidable Verification Problems for Programs with Unreliable Channels (PAA, BJ), pp. 316–327.
ICGTTAGT-1994-Klempien-Hinrichs #confluence #simulation
Node Replacement in Hypergrahps: Simulation of Hyperedge Replacement, and Decidability of Confluence (RKH), pp. 397–411.
KRKR-1994-LakemeyerM #first-order #power of
Enhancing the Power of a Decidable First-Order Reasoner (GL, SM), pp. 403–414.
OOPSLAOOPSLA-1994-EifrigSTZ #object-oriented #type system
Application of OOP Type Theory: State, Decidability, Integragtion (JE, SFS, VT, AEZ), pp. 16–30.
POPLPOPL-1994-CastagnaP #bound #quantifier
Decidable Bounded Quantification (GC, BCP), pp. 151–162.
CADECADE-1994-Prehofer #higher-order #problem #unification
Decidable Higher-Order Unification Problems (CP), pp. 635–649.
CAVCAV-1994-McManisV #automaton #hybrid
Suspension Automata: A Decidable Class of Hybrid Automata (JM, PV), pp. 105–117.
CAVCAV-1994-PuriV #difference #hybrid
Decidability of Hybrid Systems with Rectangular Differential Inclusion (AP, PV), pp. 95–104.
LICSLICS-1994-Wells #higher-order #λ-calculus
Typability and Type-Checking in the Second-Order λ-Calculus are Equivalent and Undecidable (JBW), pp. 176–185.
ICALPICALP-1993-IbarraJTW
New Decidability Results Concerning Two-way Counter Machines and Applications (OHI, TJ, NQT, HW), pp. 313–324.
ICALPICALP-1993-JiangSSY #pattern matching
Inclusion is Undecidable for Pattern Languages (TJ, AS, KS, SY), pp. 301–312.
ICALPICALP-1993-LodayaT #logic #partial order
Decidability of a Partial Order Based Temporal Logic (KL, PST), pp. 582–592.
RTARTA-1993-Senizergues #problem #termination
Some Undecidable Termination Problems for Semi-Thue Systems (GS), p. 434.
RTARTA-1993-Tajine #equation
The Negation Elimination from Syntactic Equational Formula is Decidable (MT), pp. 316–327.
TLCATLCA-1993-Urzyczyn #re-engineering
Type reconstruction in Fω is undecidable (PU), pp. 418–432.
OOPSLAOOPSLA-1993-BruceCMGDM #object-oriented #type checking
Safe and Decidable Type Checking in an Object-Oriented Language (KBB, JC, TPM, RvG, AD, RM), pp. 29–46.
CSLCSL-1993-Marcinkowski #horn clause #set
A Horn Clause that Implies and Undecidable Set of Horn Clauses (JM), pp. 223–237.
ICLPILPS-1993-DevienneLR #horn clause #problem #recursion
The Emptiness Problem of One Binary Recursive Horn Clause is Undecidable (PD, PL, JCR), pp. 250–265.
ICALPICALP-1992-Krob #multi #problem #similarity
The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable (DK), pp. 101–112.
POPLPOPL-1992-Pierce #bound #quantifier
Bounded Quantification is Undecidable (BCP), pp. 305–315.
ESOPESOP-1992-OKeefeW #type inference
Type Inference for Partial Types is Decidable (PO, MW), pp. 408–417.
CADECADE-1992-DershowitzMS #convergence
Decidable Matching for Convergent Systems (ND, SM, GS), pp. 589–602.
CAVCAV-1992-Cerans #bisimulation #parallel #process
Decidability of Bisimulation Equivalences for Parallel Timer Processes (KC), pp. 302–315.
LICSLICS-1992-ComonHJ #equation #problem
Decidable Problems in Shallow Equational Theories (HC, MH, JPJ), pp. 255–265.
LICSLICS-1992-Dowek #higher-order
Third Order Matching is Decidable (GD), pp. 2–10.
ICALPICALP-1991-DiekertOR #complexity #confluence #on the
On Confluent Semi-Commutations — Decidability and Complexity Results (VD, EO, KR), pp. 229–241.
ICALPICALP-1991-JouannaudO #satisfiability
Satisfiability of Systems of Ordinal Notations with the Subterm Property is Decidable (JPJ, MO), pp. 455–468.
RTARTA-1991-Klay
Undecidable Properties of Syntactic Theories (FK), pp. 136–149.
RTARTA-1991-Salomaa #confluence #monad #term rewriting #termination
Decidability of Confluence and Termination of Monadic Term Rewriting Systems (KS), pp. 275–286.
CAVCAV-1991-Huttel #branch #process #similarity
Silence is Golden: Branching Bisimilarity is Decidable for Context-Free Processes (HH), pp. 2–12.
ICALPICALP-1990-Choffrut
Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case (CC), pp. 490–500.
ICALPICALP-1990-Riecke #call-by #proving
A Complete and Decidable Proof System for Call-by-Value Equalities (JGR), pp. 20–31.
STOCSTOC-1990-BorodinT #on the #polynomial
On the Decidability of Sparse Univariate Polynomial Interpolation (AB, PT), pp. 535–545.
STOCSTOC-1990-HarjuK #automaton #equivalence #finite #multi
Decidability of the Multiplicity Equivalence of Multitape Finite Automata (TH, JK), pp. 477–481.
CADECADE-1990-Schwind #logic #proving #set #theorem proving
A Tableau-Based Theorem Prover for a Decidable Subset of Default Logic (CS), pp. 528–542.
LICSLICS-1990-DauchetT #formal method #term rewriting
The Theory of Ground Rewrite Systems is Decidable (MD, ST), pp. 242–248.
LICSLICS-1990-EmersonES #on the #performance
On the Limits of Efficient Temporal Decidability (EAE, ME, JS), pp. 464–475.
RTARTA-1989-Tison #termination
Fair Termination is Decidable for Ground Systems (ST), pp. 462–476.
KRKR-1989-Schmidt-Schauss
Subsumption in KL-ONE is Undecidable (MSS), pp. 421–431.
TAPSOFTCAAP-1989-HabelKV #bound #graph grammar #problem
Decidable Boundedness Problems for Hyperedge-Replacement Graph Grammar (AH, HJK, WV), pp. 275–289.
PODSPODS-1988-Vardi #bound #linear #query #recursion
Decidability and Undecidability Results for Boundedness of Linear Recursive Queries (MYV), pp. 341–351.
ICALPICALP-1988-Culik #equivalence #problem #proving
New Techniques for Proving the Decidability of Equivalence Problems (KCI), pp. 162–175.
ICALPICALP-1988-Turakainen #equivalence
The Equivalence of DGSM Replications on Q-Rational Languages is Decidable (PT), pp. 654–666.
STOCSTOC-1988-CosmadakisGKV #database #logic programming #optimisation #problem #source code
Decidable Optimization Problems for Database Logic Programs (SSC, HG, PCK, MYV), pp. 477–490.
LICSLICS-1988-MullerSS #automaton #exponential #logic #why
Weak Alternating Automata Give a Simple Explanation of Why Most Temporal and Dynamic Logics are Decidable in Exponential Time (DEM, AS, PES), pp. 422–427.
PODSPODS-1987-NaughtonS #bound #recursion
A Decidable Class of Bounded Recursions (JFN, YS), pp. 227–236.
PODSPODS-1987-Shmueli #logic #query
Decidability and Expressiveness of Logic Queries (OS), pp. 237–249.
RTARTA-1987-BurckertHS #equation #on the #unification
On Equational Theories, Unification and Decidability (HJB, AH, MSS), pp. 204–215.
LICSLICS-1987-DauchetTHL #confluence #term rewriting
Decidability of the Confluence of Ground Term Rewriting Systems (MD, ST, TH, PL), pp. 353–359.
LICSLICS-1987-GaifmanMSV #database #logic programming #optimisation #problem #source code
Undecidable Optimization Problems for Database Logic Programs (HG, HGM, YS, MYV), pp. 106–115.
LICSLICS-1986-PerrinS #automaton #equivalence #integer #monad
Automata on the Integers, Recurrence Distinguishability, and the Equivalence and Decidability of Monadic Theories (DP, PES), pp. 301–304.
ICALPICALP-1984-ChazelleOSW #complexity
The Complexity and Decidability of Separation (BC, TO, ESS, DW), pp. 119–127.
STOCSTOC-1983-Feldman #logic #probability
A Decidable Propositional Probabilistic Dynamic Logic (YAF), pp. 298–309.
STOCSTOC-1982-Kosaraju #reachability
Decidability of Reachability in Vector Addition Systems (SRK), pp. 267–281.
ICALPICALP-1981-HeintzS #polynomial #random
Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables (JH, MS), pp. 16–28.
POPLPOPL-1981-Pratt #logic
Program Logic Without Binding is Decidable (VRP), pp. 159–163.
STOCSTOC-1981-CulikH #equivalence #problem
The ω-Sequence Equivalence Problem for DOL Systems Is Decidable (KCI, TH), pp. 1–6.
STOCSTOC-1980-KannanL #problem
The Orbit Problem is Decidable (RK, RJL), pp. 252–261.
ICALPICALP-1979-Wegner #approach #two-level grammar
Bracketed Two-Level Grammars — A Decidable and Practical Approach to Language Definitions (LMW), pp. 668–682.
ICALPICALP-1977-CulikF #equivalence #problem #sequence
The Sequence Equivalence Problem for D0L Systems is Decidable (KCI, IF), pp. 148–163.
ICALPICALP-1977-Walter #context-free grammar #equivalence
Structural Equivalence of Context-Free Grammar Forms is Decidable (HKGW), pp. 539–553.
STOCSTOC-1977-SacerdoteT #problem #reachability
The Decidability of the Reachability Problem for Vector Addition Systems (GSS, RLT), pp. 61–76.
ICALPICALP-1976-Valiant #equivalence #problem
The Equivalence Problem for DOL Systems and its Decidability for Binary Alphabets (LGV), pp. 31–37.
ICALPICALP-1974-Bertsch
A Decidability Result for Sequential Grammars (EB), pp. 577–583.
ICALPICALP-1974-Mehlhorn #recursion
The “Almost All” Theory of Subrecursive Degrees is Decidable (KM), pp. 317–325.
STOCSTOC-1974-Valiant #automaton #equivalence
The Decidability of Equivalence for Deterministic Finite-Turn Pushdown Automata (LGV), pp. 27–32.
STOCSTOC-1972-ConstableM #equivalence #problem #recursion
Subrecursive Program Schemata I & II: I. Undecidable Equivalence Problems; II. Decidable Equivalence Problems (RLC, SSM), pp. 1–17.
STOCSTOC-1970-Cudia #problem
The Degree Hierarchy of Undecidable Problems of Formal Grammars (DFC), pp. 10–21.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.