Results 11 to 20 of about 39,716 (258)
General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond [PDF]
Logical Methods in Computer Science, 2022 The model of asynchronous programming arises in many contexts, from low-level systems software to high-level web programming. We take a language-theoretic perspective and show general decidability and undecidability results for asynchronous programs that
Rupak Majumdar +2 more
doaj +2 more sources
Decidability Results for the Boundedness Problem [PDF]
Logical Methods in Computer Science, 2014 We prove decidability of the boundedness problem for monadic least fixed-point recursion based on positive monadic second-order (MSO) formulae over trees.
Blumensath, Achim +2 more
core +2 more sources
Decidability of higher-order matching [PDF]
Logical Methods in Computer Science, 2009 We show that the higher-order matching problem is decidable using a game-theoretic argument.Comment: appears in LMCS (Logical Methods in Computer ...
Colin Stirling +5 more
core +6 more sources
Philosophies, 2023 The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that ...
Nathan Salmon
doaj +1 more source
Decidability Preservation and Complexity Bounds for Combined Logics
Mathematics, 2022 Transfer theorems for combined logics provide essential tools and insight for reasoning about complex logical systems. In this paper, we present the first sufficient criterion (contextual extensibility) for decidability to be preserved through ...
Carlos Caleiro, Sérgio Marcelino
doaj +1 more source
Resynchronized Uniformization and Definability Problems for Rational Relations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Regular synchronization languages can be used to define rational relations of finite words, and to characterize subclasses of rational relations, like automatic or recognizable relations.
Christof Löding, Sarah Winter
doaj +1 more source
E-unification by means of tree tuple synchronized grammars [PDF]
Discrete Mathematics & Theoretical Computer Science, 1997 The goal of this paper is both to give an E-unification procedure that always terminates, and to decide unifiability. For this, we assume that the equational theory is specified by a confluent and constructor-based rewrite system, and that four ...
Sébastien Limet, Pierre Réty
doaj +1 more source
Robustly Complete Finite-State Abstractions for Control Synthesis of Stochastic Systems
IEEE Open Journal of Control Systems, 2023 The essential step of abstraction-based control synthesis for nonlinear systems to satisfy a given specification is to obtain a finite-state abstraction of the original systems.
Yiming Meng, Jun Liu
doaj +1 more source
Karp-Miller Trees for a Branching Extension of VASS [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We study BVASS (Branching VASS) which extend VASS (Vector Addition Systems with States) by allowing addition transitions that merge two configurations. Runs in BVASS are tree-like structures instead of linear ones as for VASS.
Kumar Neeraj Verma +1 more
doaj +2 more sources
Decidability for the theory of modules over a Prüfer domain [PDF]
, 2021 In this paper we give elementary conditions completely characterising when the theory of modules of a Pr\"ufer domain is decidable. Using these results, we show that the theory of modules of the ring of integer valued polynomials is decidable.
arxiv +1 more source