75 citations
- Université Paris CitéFR54 papers
- Centre National de la Recherche ScientifiqueFR28 papers
- Délégation Paris 7FR9 papers
- Institut national de recherche en sciences et technologies du numériqueFR9 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR8 papers
- Laboratoire d'Informatique de l'École PolytechniqueFR5 papers
- École Normale Supérieure de LyonFR4 papers
- Sorbonne UniversitéFR4 papers
- École PolytechniqueFR3 papers
- Laboratoire d'Informatique, de Robotique et de Microélectronique de MontpellierFR3 papers
- Orange (France)FR3 papers
- Université de MontpellierFR3 papers
5 papers · 1 filter
Pushing undecidability of the isolation problem for probabilistic automata
Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj
This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable…
Splicing systems and the Chomsky hierarchy
Jean Berstel, Luc Boasson, Isabelle Fagnot
In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. Th…
Negative bases and automata
Christiane Frougny, Anna Chiara Lai
We study expansions in non-integer negative base -β introduced by Ito and Sadahiro. Using countable automata associated with (-β)-expansions, we characterize the case where the (-β…
A non-ergodic probabilistic cellular automaton with a unique invariant measure
Philippe Chassaing, Jean Mairesse
We exhibit a Probabilistic Cellular Automaton (PCA) on the integers with an alphabet and a neighborhood of size 2 which is non-ergodic although it has a unique invariant measure. T…
Evolving MultiAlgebras unify all usual sequential computation models
Serge Grigorieff, Pierre Valarcher
It is well-known that Abstract State Machines (ASMs) can simulate "step-by-step" any type of machines (Turing machines, RAMs, etc.). We aim to overcome two facts: 1) simulation is…