Regularity of languages defined by formal series with isolated cut point
Bertoni, Alberto ; Bianchi, Maria Paola ; D’Alessandro, Flavi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 479-493 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2012019
Classification:  68Q45,  68Q70 
@article{ITA_2012__46_4_479_0,
     author = {Bertoni, Alberto and Bianchi, Maria Paola and D'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},
     volume = {46},
     year = {2012},
     pages = {479-493},
     doi = {10.1051/ita/2012019},
     mrnumber = {3107860},
     zbl = {1279.68131},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 479-493. doi : 10.1051/ita/2012019. http://gdmltest.u-ga.fr/item/ITA_2012__46_4_479_0/

[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 1318966 | Zbl 0803.68073

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

[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 386897 | Zbl 0327.94069

[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 460000 | Zbl 0366.94064

[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 2053870 | Zbl 1037.68058

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

[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 2165750 | Zbl 1078.81012

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

[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 152391 | Zbl 0148.00804

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

[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 1069095 | Zbl 0711.68075

[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 652738 | Zbl 0486.68045

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

[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 1129905 | Zbl 0766.68098

[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 289222 | Zbl 0234.94055

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

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

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

[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 929097 | Zbl 0635.10007