Results 11 to 20 of about 47,932 (337)
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 +3 more sources
Decidability of Definability [PDF]
2011 IEEE 26th Annual Symposium on Logic in Computer Science, 2011 AbstractFor a fixed countably infinite structure Γ with finite relational signature τ, we study the following computational problem: input are quantifier-free τ-formulas ϕ0, ϕ1, …, ϕn that define relations R0, R1, …, Rn over Γ. The question is whether the relation R0 is primitive positive definable from R1, …, Rn, i.e., definable by a first-order ...
Manuel Bodirsky +2 more
openaire +4 more sources
DECIDING ON WHAT TO DECIDE [PDF]
International Economic Review, 2017 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 +6 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
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
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
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
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
Termination of Triangular Integer Loops is Decidable [PDF]
, 2019 We consider the problem whether termination of affine integer loops is decidable. Since Tiwari conjectured decidability in 2004, only special cases have been solved.
A Tiwari +7 more
core +3 more sources
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