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
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
Lengths May Break Privacy – Or How to Check for Equivalences with Length [PDF]
, 2013 Security protocols have been successfully analyzed using symbolic models, where messages are represented by terms and protocols by processes. Privacy properties like anonymity or untraceability are typically expressed as equivalence between processes ...
A. Armando +4 more
core +4 more sources
Decidability of the Clark's Completion Semantics for Monadic Programs and Queries [PDF]
, 2014 There are many different semantics for general logic programs (i.e. programs that use negation in the bodies of clauses). Most of these semantics are Turing complete (in a sense that can be made precise), implying that they are undecidable.
Haykazyan, Levon
core +1 more source
A new proof for the decidability of D0L ultimate periodicity
, 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.Comment: In Proceedings WORDS 2011, arXiv:1108 ...
A. Ehrenfeucht +15 more
core +2 more sources
Decidability of the Monadic Shallow Linear First-Order Fragment with Straight Dismatching Constraints [PDF]
, 2017 The monadic shallow linear Horn fragment is well-known to be decidable and has many application, e.g., in security protocol analysis, tree automata, or abstraction refinement. It was a long standing open problem how to extend the fragment to the non-Horn
A Teucke +18 more
core +3 more sources
Decision Problems for Deterministic Pushdown Automata on Infinite Words
, 2014 The article surveys some decidability results for DPDAs on infinite words (omega-DPDA). We summarize some recent results on the decidability of the regularity and the equivalence problem for the class of weak omega-DPDAs. Furthermore, we present some new
Löding, Christof
core +2 more sources
Alternating register automata on finite words and trees [PDF]
, 2012 We study alternating register automata on data words and data trees in relation to logics. A data word (resp. data tree) is a word (resp. tree) whose every position carries a label from a finite alphabet and a data value from an infinite domain.
Figueira, Diego
core +4 more sources
Dendritic cells steering antigen and leukocyte traffic in lymph nodes
FEBS Letters, EarlyView.Dendritic cells are key players in the activation of T cells and their commitment to effector function. In this In a Nutshell Review, we will discuss how dendritic cells guide the trafficking of antigen and leukocytes in the lymph node, thus influencing T‐cell activation processes. Dendritic cells (DCs) play a central role in initiating and shaping the
Enrico Dotta +3 more
wiley +1 more source
Decidability of All Minimal Models (Revised Version - 2012) [PDF]
, 2012 This unpublished note is an alternate, shorter (and hopefully more readable) proof of the decidability of all minimal models. The decidability follows from a proof of the existence of a cellular term in each observational equivalence class of a minimal ...
Padovani, Vincent
core +3 more sources