Results 11 to 20 of about 7,198 (311)
Decidability of DPDA equivalence
Theoretical Computer Science, 2001 A proof of decidability of equivalence between deterministic pushdown automata is presented using a mixture of methods developed in concurrency and language theory.
Colin Stirling
exaly +2 more sources
A new proof for the decidability of D0L ultimate periodicity [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 We give a new proof for the decidability of the D0L ultimate periodicity problem based on the decidability of p-periodicity of morphic words adapted to the approach of Harju and ...
Tero Harju, Tomi Kärki, Vesa Halava
core +2 more sources
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 +1 more source
DECIDING ON WHAT TO DECIDE [PDF]
International Economic Review, 2021 AbstractWe study two‐stage collective decision‐making procedures where in the first stage, part of the voters decide what issues will be put in the agenda and in the second stage, the whole set of voters decides on the positions to be adopted regarding the issues that are in the agenda.
Barberà, Salvador, Gerber, Anke
openaire +5 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.
Achim Blumensath +5 more
core +2 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
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
Trustworthy AI: Deciding What to Decide [PDF]
CoRR, 2023 Cloud-Based Computational Decision By Leveraging Artificial Ultra ...
WU, Caesar (ming-wei) +4 more
openaire +3 more sources
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
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