Regularity of languages defined by formal series with isolated cut point
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 479-493.

Let Lϕ,λ = {ω ∈ Σ∗ | ϕ(ω) > λ} be the language recognized by a formal series ϕ:Σ∗ → ℝ with isolated cut point λ. We provide new conditions that guarantee the regularity of the language Lϕ,λ in the case that ϕ is rational or ϕ is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.

DOI : 10.1051/ita/2012019
Classification : 68Q45, 68Q70
Mots-clés : formal power series, Hadamard quotient, regular languages 
@article{ITA_2012__46_4_479_0,
     author = {Bertoni, Alberto and Bianchi, Maria Paola and D{\textquoteright}Alessandro, Flavi},
     title = {Regularity of languages defined by formal series with isolated cut point},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {479--493},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {4},
     year = {2012},
     doi = {10.1051/ita/2012019},
     mrnumber = {3107860},
     zbl = {1279.68131},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2012019/}
}
TY  - JOUR
AU  - Bertoni, Alberto
AU  - Bianchi, Maria Paola
AU  - D’Alessandro, Flavi
TI  - Regularity of languages defined by formal series with isolated cut point
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
SP  - 479
EP  - 493
VL  - 46
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2012019/
DO  - 10.1051/ita/2012019
LA  - en
ID  - ITA_2012__46_4_479_0
ER  - 
%0 Journal Article
%A Bertoni, Alberto
%A Bianchi, Maria Paola
%A D’Alessandro, Flavi
%T Regularity of languages defined by formal series with isolated cut point
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 479-493
%V 46
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2012019/
%R 10.1051/ita/2012019
%G en
%F ITA_2012__46_4_479_0
Bertoni, Alberto; Bianchi, Maria Paola; D’Alessandro, Flavi. Regularity of languages defined by formal series with isolated cut point. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 479-493. doi : 10.1051/ita/2012019. http://archive.numdam.org/articles/10.1051/ita/2012019/

[1] M. Anselmo and A. Bertoni, On 2pfas and the Hadamard quotient of formal power series. Bull. Belg. Math. Soc. 1 (1994) 165-173. | MR | Zbl

[2] J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988). | MR | Zbl

[3] A. Bertoni, The solution of problems relative to probabilistic automata in the frame of the formal languages theory, in Vierte Jahrestagung der Gesellschaft for Informatik. Lect. Notes Comput. Sci. 26 (1975) 107-112. | MR | Zbl

[4] A. Bertoni, G. Mauri and M. Torelli, Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata, in Proc. of 4th International Colloquium on Automata, Languages and Programming. Lect. Notes Comput. Sci. 52 (1977) 87-94. | MR | Zbl

[5] A. Bertoni, C. Mereghetti and B. Palano, Quantum Computing : 1-Way Quantum Automata, in Proc. of Developments in Language Theory. Lect. Notes Comput. Sci. (2003) 1-20. | MR | Zbl

[6] V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst. 36 (2003) 231-245. | MR | Zbl

[7] V.D. Blondel, E. Jeandel, P. Koiran and N. Portier, Decidable and undecidable problems about quantum automata. SIAM J. Comput. 34 (2005) 1464-1473 | MR | Zbl

[8] A. Brodsky and N. Pippenger, Characterization of 1-way quantum finite automata. Available on http://xxx.lanl.gov/abs/quant-ph/9903014. | Zbl

[9] C. Choffrut, Private communication to the authors, July 2011.

[10] N. Chomsky and M.P. Schützenberger, The Algebraic Theory of Context-Free Languages, in Computer Programming and Formal Systems. North-Holland, Amsterdam (1963). | MR | Zbl

[11] M. Droste, W. Kuich and H. Vogler, Handbook of weighted automata. EATCS Series Springer (2009). | MR | Zbl

[12] C. Dwork and L. Stockmeyer, A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput. 19 (1990) 1011-1023. | MR | Zbl

[13] R. Freivalds, Probabilistic Two-way Machines, in Proc. of Int. Symp. Math. Found. Comput. Sci. Lect. Notes Comput. Sci. 118 (1981) 33-45. | MR | Zbl

[14] G. Jacob, La finitude des représentations linéaires des semigoupes est décidable. J. Algebra 52 (1978) 437-459. | MR | Zbl

[15] J. Kaneps and R. Freivalds, Running time to recognize nonregular languages by two-way probabilistic automata, in Proc. of ICALP 91. Lect. Notes Comput. Sci. 510 (1991) 174-185. | MR | Zbl

[16] O. Madani, S. Hanks and A. Condon, On the undecidability of probabilistic planning and infinite-horizon partially observable markov decision problems, in Proc. of the 6th National Conference on Artificial Intelligence (1999).

[17] A. Paz, Introduction to Probabilistic Automata. Academic Press (1971). | MR | Zbl

[18] M. Rabin, Probabilistic automata. Inf. Control 6 (1963) 230-245. | Zbl

[19] A. Salomaa and M. Soittola, Automata-theoretic aspects of formal power series. Springer (1978). | MR | Zbl

[20] M.P. Schützenberger, On the definition of a family of automata. Inf. Control 4 (1961) 245-270. | MR | Zbl

[21] A.J. Van Der Poorten, Solution de la conjecture de Pisot sur le quotient de Hadamard de deux fractions rationnelles. C. R. Acad. Sci. Paris, Sér. I 306 (1988) 97-102. | MR | Zbl

Cité par Sources :