Geodesic
A B\"uchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4.

Voir la notice de l'article provenant de la source Episciences

We introduce MSO graph storage types, and call a storage type MSO-expressible if it is isomorphic to some MSO graph storage type. An MSO graph storage type has MSO-definable sets of graphs as storage configurations and as storage transformations. We consider sequential automata with MSO graph storage and associate with each such automaton a string language (in the usual way) and a graph language; a graph is accepted by the automaton if it represents a correct sequence of storage configurations for a given input string. For each MSO graph storage type, we define an MSO logic which is a subset of the usual MSO logic on graphs. We prove a B\"uchi-Elgot-Trakhtenbrot theorem, both for the string case and the graph case. Moreover, we prove that (i) each MSO graph transduction can be used as storage transformation in an MSO graph storage type, (ii) every automatic storage type is MSO-expressible, and (iii) the pushdown operator on storage types preserves the property of MSO-expressibility. Thus, the iterated pushdown storage types are MSO-expressible.
DOI : 10.23638/DMTCS-22-4-3
Classification : 03D05, 68Q45 
@article{DMTCS_2020_22_4_a3,
     author = {Engelfriet, Joost and Vogler, Heiko},
     title = {A {B\"uchi-Elgot-Trakhtenbrot} theorem for automata with {MSO} graph storage},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-4-3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-3/}
}
TY  - JOUR
AU  - Engelfriet, Joost
AU  - Vogler, Heiko
TI  - A B\"uchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-3/
DO  - 10.23638/DMTCS-22-4-3
LA  - en
ID  - DMTCS_2020_22_4_a3
ER  - 
%0 Journal Article
%A Engelfriet, Joost
%A Vogler, Heiko
%T A B\"uchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-3/
%R 10.23638/DMTCS-22-4-3
%G en
%F DMTCS_2020_22_4_a3
Engelfriet, Joost; Vogler, Heiko. A B\"uchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4. doi : 10.23638/DMTCS-22-4-3. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-3/

Cité par Sources :