75 papers:
FoSSaCS-2015-Velner #decidability #game studies #multi #robust- Robust Multidimensional Mean-Payoff Games are Undecidable (YV), pp. 312–327.
LATA-2015-KrishnaMT #automaton #bound #decidability #problem #reachability #recursion- Time-Bounded Reachability Problem for Recursive Timed Automata is Undecidable (SNK, LM, AT), pp. 237–248.
LICS-2015-GogaczM #decidability #query- The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable (TG, JM), pp. 281–292.
TLCA-2015-CastellanCD #similarity- Undecidability of Equality in the Free Locally Cartesian Closed Category (SC, PC, PD), pp. 138–152.
ICALP-v2-2014-GogaczM #decidability #termination- All-Instances Termination of Chase is Undecidable (TG, JM), pp. 293–304.
STOC-2013-CadekKMVW- Extending continuous maps: polynomiality and undecidability (MC, MK, JM, LV, UW), pp. 595–604.
CIAA-2013-MrazO #automaton #decidability- λ-Confluence Is Undecidable for Clearing Restarting Automata (FM, FO), pp. 256–267.
KR-2012-BorgwardtP #fuzzy #logic- Undecidability of Fuzzy Description Logics (SB, RP).
CSL-2012-KuusistoMV #decidability #first-order #geometry- Undecidable First-Order Theories of Affine Geometries (AK, JM, JV), pp. 470–484.
DLT-J-2010-BordihnKM11 #automaton #communication #finite #parallel- Undecidability and Hierarchy Results for Parallel Communicating Finite Automata (HB, MK, AM), pp. 1577–1592.
- LATA-2011-SalomaaSY #complexity
- Undecidability of the State Complexity of Composed Regular Operations (AS, KS, SY), pp. 489–498.
- LICS-2011-MarcinkowskiM #logic
- The Ultimate Undecidability Result for the Halpern-Shoham Logic (JM, JM), pp. 377–386.
- DLT-2010-BordihnKM #automaton #communication #finite #parallel
- Undecidability and Hierarchy Results for Parallel Communicating Finite Automata (HB, MK, AM), pp. 88–99.
- ICALP-v2-2010-GimbertO #automaton #decidability #finite #probability #problem #word
- Probabilistic Automata on Finite Words: Decidable and Undecidable Problems (HG, YO), pp. 527–538.
- ICALP-v2-2010-MarcinkowskiMK #decidability #logic
- B and D Are Enough to Make the Halpern-Shoham Logic Undecidable (JM, JM, EK), pp. 357–368.
- LICS-2010-BrotherstonK #logic
- Undecidability of Propositional Separation Logic and Its Neighbours (JB, MIK), pp. 130–139.
- LICS-2010-Larchey-WendlingG #semantics
- The Undecidability of Boolean BI through Phase Semantics (DLW, DG), pp. 140–149.
RTA-2010-FujitaS #problem #system f- The Undecidability of Type Related Problems in Type-free Style System F (KeF, AS), pp. 103–118.
- LATA-2009-BordihnHK #problem #subclass
- Undecidability of Operation Problems for T0L Languages and Subclasses (HB, MH, MK), pp. 236–246.
- LATA-2009-Moore #data access #documentation #generative #problem
- The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates (NM), pp. 601–613.
- CSL-2009-EndrullisGZ #term rewriting
- Degrees of Undecidability in Term Rewriting (JE, HG, HZ), pp. 255–270.
- DLT-2008-Jancar #decidability #similarity
- Selected Ideas Used for Decidability and Undecidability of Bisimilarity (PJ), pp. 56–71.
PPDP-2008-OlarteV #monad #security- The expressivity of universal timed CCP: undecidability of Monadic FLTL and closure operators for security (CO, FDV), pp. 8–19.
- CSL-2008-HodkinsonMS #axiom #logic
- Non-finite Axiomatizability and Undecidability of Interval Temporal Logics with C, D, and T (IMH, AM, GS), pp. 308–322.
- CSL-2008-NakazawaTKN #λ-calculus
- Undecidability of Type-Checking in Domain-Free Typed λ-Calculi with Existence (KN, MT, YK, HN), pp. 478–492.
- ICALP-2007-KobayashiS #behaviour #calculus #type system
- Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the π -Calculus (NK, TS), pp. 740–751.
- FoSSaCS-2006-JancarS #similarity #term rewriting
- Undecidability Results for Bisimilarity on Prefix Rewrite Systems (PJ, JS), pp. 277–291.
- DLT-2006-BellP #bound #matrix
- Lowering Undecidability Bounds for Decision Questions in Matrices (PB, IP), pp. 375–385.
IJCAR-2006-BonacinaGNRZ #decidability- Decidability and Undecidability Results for Nelson-Oppen and Rewrite-Based Decision Procedures (MPB, SG, EN, SR, DZ), pp. 513–527.
ITiCSE-2004-Gal-EzerLS04a- Introducing undecidability (JGE, DL, DS), p. 276.
- FoSSaCS-2004-ConfortiG #decidability
- Decidability of Freshness, Undecidability of Revelation (GC, GG), pp. 105–120.
TACAS-2004-KrcalY #analysis #automaton #decidability #problem #scheduling #using- Decidable and Undecidable Problems in Schedulability Analysis Using Timed Automata (PK, WY), pp. 236–250.
- CSL-2004-ImmermanRRSY #bound #decidability #logic #transitive
- The Boundary Between Decidability and Undecidability for Transitive-Closure Logics (NI, AMR, TWR, SS, GY), pp. 160–174.
SAS-2003-KuncakR #abstraction #decidability- Existential Heap Abstraction Entailment Is Undecidable (VK, MCR), pp. 418–438.
- ICALP-2003-Mayr #bisimulation #equivalence #process
- Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes (RM), pp. 570–583.
- DLT-2002-Srba #similarity
- Undecidability of Weak Bisimilarity for PA-Processes (JS), pp. 197–208.
- LICS-2002-HodkinsonWZ #branch #decidability #first-order #logic
- Decidable and Undecidable Fragments of First-Order Branching Temporal Logics (IMH, FW, MZ), pp. 393–402.
- DLT-2001-HalavaH #morphism
- An Undecidability Result Concerning Periodic Morphisms (VH, TH), pp. 304–310.
- ICALP-2001-Kunc #decidability #problem
- The Trace Coding Problem Is Undecidable (MK), pp. 603–614.
IWPC-1999-HarmanFHBD #approximate #decidability- Program Simplification as a Means of Approximating Undecidable Propositions (MH, CF, RMH, DB, SD), pp. 208–217.
- STOC-1999-AmanoI #automaton #finite #quantum
- Undecidability on Quantum Finite Automata (MA, KI), pp. 368–375.
- RTA-1999-Marcinkowski #algebra #formal method
- Undecidability of the exists*forall* Part of the Theory of Ground Term Algebra Modulo an AC Symbol (JM), pp. 92–102.
PODS-1998-BaileyDR #database #decidability #problem #termination- Decidability and Undecidability Results for the Termination Problem of Active Database Rules (JB, GD, KR), pp. 264–273.
- STOC-1998-Freedman #satisfiability
- K-sat on Groups and Undecidability (MHF), pp. 572–576.
- ICALP-1998-DufourdFS #decidability
- Reset Nets Between Decidability and Undecidability (CD, AF, PS), pp. 103–115.
- KR-1998-Dornheim
- Undecidability of Plane Polygonal Mereotopology (CD), pp. 342–355.
- RTA-1998-Levy #decidability #higher-order #problem #unification
- Decidable and Undecidable Second-Order Unification Problems (JL), pp. 47–60.
- ICALP-1997-NarendranO #confluence #decidability #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.
- RTA-1997-Marcinkowski #first-order
- Undecidability of the First Order Theory of One-Step Right Ground Rewriting (JM), pp. 241–253.
- RTA-1997-Vorobyov #decidability #first-order #linear
- The First-Order Theory of One Step Rewriting in Linear Noetherian Systems is Undecidable (SGV), pp. 254–268.
- TLCA-1997-MalolepszyMZ #decidability
- Schwichtenberg-Style λ Definability Is Undecidable (JM, MM, MZ), pp. 267–283.
- CSL-1996-GeserMOZ #term rewriting
- Relative Undecidability in Term Rewriting (AG, AM, EO, HZ), pp. 150–166.
- CSL-1996-Yashin #logic #problem
- New Intuitionistic Logical Constants: Undecidability of the Conservativsness Problem (ADY), pp. 460–471.
- LICS-1996-Marcinkowski #bound #datalog #decidability
- DATALOG SIRUPs Uniform Boundedness is Undecidable (JM), pp. 13–24.
- LICS-1996-TiurynU #decidability #higher-order #problem #type system
- The Subtyping Problem for Second-Order Types is Undecidable (JT, PU), pp. 74–85.
- RTA-1996-Treinen #decidability #first-order
- The First-Order Theory of One-Step Rewriting is Undecidable (RT), pp. 276–286.
- DLT-1995-Jedrzejowicz #decidability #problem
- An Undecidable Problem for Shuffle Languages (JJ), pp. 112–118.
- ICALP-1994-AbdullaJ #decidability #problem #source code #verification
- Undecidable Verification Problems for Programs with Unreliable Channels (PAA, BJ), pp. 316–327.
- LICS-1994-Wells #decidability #higher-order #λ-calculus
- Typability and Type-Checking in the Second-Order λ-Calculus are Equivalent and Undecidable (JBW), pp. 176–185.
- ICALP-1993-JiangSSY #decidability #pattern matching
- Inclusion is Undecidable for Pattern Languages (TJ, AS, KS, SY), pp. 301–312.
- CSL-1993-Marcinkowski #decidability #horn clause #set
- A Horn Clause that Implies and Undecidable Set of Horn Clauses (JM), pp. 223–237.
ILPS-1993-DevienneLR #decidability #horn clause #problem #recursion- The Emptiness Problem of One Binary Recursive Horn Clause is Undecidable (PD, PL, JCR), pp. 250–265.
- RTA-1993-Senizergues #decidability #problem #termination
- Some Undecidable Termination Problems for Semi-Thue Systems (Abstract) (GS), p. 434.
- TLCA-1993-Dowek #calculus
- The Undecidability of Typability in the λ-π-Calculus (GD), pp. 139–145.
- TLCA-1993-Urzyczyn #decidability #re-engineering
- Type reconstruction in Fω is undecidable (PU), pp. 418–432.
- ICALP-1992-Krob #decidability #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 #decidability #quantifier- Bounded Quantification is Undecidable (BCP), pp. 305–315.
- RTA-1991-Klay #decidability
- Undecidable Properties of Syntactic Theories (FK), pp. 136–149.
- STOC-1990-KfouryTU #problem
- The Undecidability of the Semi-Unification Problem (Preliminary Report) (AJK, JT, PU), pp. 468–476.
- KR-1989-Schmidt-Schauss #decidability
- Subsumption in KL-ONE is Undecidable (MSS), pp. 421–431.
- PODS-1988-Vardi #bound #decidability #linear #query #recursion
- Decidability and Undecidability Results for Boundedness of Linear Recursive Queries (MYV), pp. 341–351.
- LICS-1987-GaifmanMSV #database #decidability #logic programming #optimisation #problem #source code
- Undecidable Optimization Problems for Database Logic Programs (HG, HGM, YS, MYV), pp. 106–115.
- ILPC-1982-Blair82
- The Undecidability of Two Completeness Notions for the “Negation as Failure” (HAB), pp. 164–168.
- STOC-1972-ConstableM #decidability #equivalence #problem #recursion
- Subrecursive Program Schemata I & II: I. Undecidable Equivalence Problems; II. Decidable Equivalence Problems (RLC, SSM), pp. 1–17.
- STOC-1970-Cudia #decidability #problem
- The Degree Hierarchy of Undecidable Problems of Formal Grammars (DFC), pp. 10–21.
