Results 21 to 30 of about 491,607 (366)
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
Improved Undecidability Results for Reachability Games on Recursive Timed Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We study reachability games on recursive timed automata (RTA) that generalize Alur-Dill timed automata with recursive procedure invocation mechanism similar to recursive state machines. It is known that deciding the winner in reachability games on RTA is
Shankara Narayanan Krishna +2 more
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
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
Undecidable problems concerning densities of languages [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the ...
Jakub Kozik
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
The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable [PDF]
, 2012 We prove that a semigroup generated by a reversible two-state Mealy automaton is either finite or free of rank 2. This fact leads to the decidability of finiteness for groups generated by two-state or two-letter invertible-reversible Mealy automata and ...
Klimann, Ines
core +8 more sources
Analysis of cryptographic protocols using logics of belief: an overview
Journal of Telecommunications and Information Technology, 2002 When designing a cryptographic protocol or explaining it, one often uses arguments such as ``since this message was signed by machine B, machine A can be sure it came from B`` in informal proofs justifying how the protocol works.
David Monniaux
doaj +1 more source
Number conserving cellular automata: new results on decidability and dynamics [PDF]
Discrete Mathematics & Theoretical Computer Science, 2003 This paper is a survey on our recent results about number conserving cellular automata. First, we prove the linear time decidability of the property of number conservation. The sequel focuses on dynamical evolutions of number conserving cellular automata.
Bruno Durand +3 more
doaj +1 more source
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