Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Guillon, Bruno"'
We show that given a graph G we can CMSO-transduce its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using orde
Externí odkaz:
http://arxiv.org/abs/2412.04970
It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine works in linear tim
Externí odkaz:
http://arxiv.org/abs/2103.05486
In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the quest
Externí odkaz:
http://arxiv.org/abs/2103.05485
Publikováno v:
In Information and Computation June 2023 292
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 1 (February 11, 2020) lmcs:5059
We prove the undecidability of MSO on $\omega$-words extended with the second-order predicate $U_1(X)$ which says that the distance between consecutive positions in a set $X \subseteq \mathbb{N}$ is unbounded. This is achieved by showing that adding
Externí odkaz:
http://arxiv.org/abs/1807.08506
We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right while incrementing or decrementing a fixed number of counters. The two
Externí odkaz:
http://arxiv.org/abs/1804.03582
Publikováno v:
In Information and Computation November 2022 289 Part A
Publikováno v:
In Information and Computation December 2021 281
Autor:
Guillon, Bruno, Prigioniero, Luca
Publikováno v:
In Theoretical Computer Science 17 December 2019 798:95-108
The question of the state-size cost for simulation of two-way nondeterministic automata (2NFAs) by two-way deterministic automata (2DFAs) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restr
Externí odkaz:
http://arxiv.org/abs/1110.1263