Decidability of Non-interactive Simulation of Joint Distributions [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2016 We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions P(x, y) and Q(u, v): The goal is to ...
Badih Ghazi, Pritish Kamath, M. Sudan
semanticscholar +1 more source
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 Linna.
Vesa Halava, Tero Harju, Tomi Kärki
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
Decidability of the Membership Problem for 2 × 2 integer matrices [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2016 The main result of this paper is the decidability of the membership problem for 2 × 2 nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular 2 × 2 integer matrices M1, . . .
I. Potapov, P. Semukhin
semanticscholar +1 more source
Decidability and Combination Results for Two Notions of Knowledge in Security Protocols
Journal of Automated Reasoning, 2012 V. Cortier, S. Delaune
exaly +2 more sources
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
Reachability and liveness in parametric timed automata [PDF]
Logical Methods in Computer Science, 2022 We study timed systems in which some timing features are unknown parameters. Parametric timed automata (PTAs) are a classical formalism for such systems but for which most interesting problems are undecidable.
Étienne André +2 more
doaj +1 more source
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
Da metamatemática para a ciência cognitiva From metamathematics to Cognitive Science
Trans/Form/Ação, 1999 Neste artigo, propõe-se uma configuração possível para a transição histórico-filosófica de temas investigados no domínio da metamatemática para o domínio da Ciência Cognitiva funcionalista neurocomputacional. A descrição de tal transição é feita por meio
Henrique de Morais Ribeiro
doaj +1 more source
Modularity for decidability of deductive verification with applications to distributed systems
ACM-SIGPLAN Symposium on Programming Language Design and Implementation, 2018 Proof automation can substantially increase productivity in formal verification of complex systems. However, unpredictablility of automated provers in handling quantified formulas presents a major hurdle to usability of these tools.
Marcelo Taube +7 more
semanticscholar +1 more source