Voir la notice de l'article provenant de la source Numdam
In this paper, we define k-counting automata as recognizers for ω-languages, i.e. languages of infinite words. We prove that the class of ω-languages they recognize is a proper extension of the ω-regular languages. In addition we prove that languages recognized by k-counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for k-counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe so.
@article{ITA_2012__46_4_461_0,
author = {Allred, Jo\"el and Ultes-Nitsche, Ulrich},
title = {$k$-counting automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {461--478},
publisher = {EDP-Sciences},
volume = {46},
number = {4},
year = {2012},
doi = {10.1051/ita/2012021},
zbl = {1279.68126},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012021/}
}
TY - JOUR AU - Allred, Joël AU - Ultes-Nitsche, Ulrich TI - $k$-counting automata JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 461 EP - 478 VL - 46 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012021/ DO - 10.1051/ita/2012021 LA - en ID - ITA_2012__46_4_461_0 ER -
%0 Journal Article %A Allred, Joël %A Ultes-Nitsche, Ulrich %T $k$-counting automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 461-478 %V 46 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012021/ %R 10.1051/ita/2012021 %G en %F ITA_2012__46_4_461_0
Allred, Joël; Ultes-Nitsche, Ulrich. $k$-counting automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 461-478. doi: 10.1051/ita/2012021
Cité par Sources :