BibSLEIGH — decidability tag

decidability

decidability

Tag #decidability

329 papers:

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