# Regularity of languages defined by formal series with isolated cut point∗

Alberto Bertoni; Maria Paola Bianchi; Flavi D’Alessandro

RAIRO - Theoretical Informatics and Applications (2012)

- Volume: 46, Issue: 4, page 479-493
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBertoni, Alberto, Bianchi, Maria Paola, and D’Alessandro, Flavi. "Regularity of languages defined by formal series with isolated cut point∗." RAIRO - Theoretical Informatics and Applications 46.4 (2012): 479-493. <http://eudml.org/doc/277838>.

@article{Bertoni2012,

abstract = {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.},

author = {Bertoni, Alberto, Bianchi, Maria Paola, D’Alessandro, Flavi},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Formal power series; Hadamard quotient; regular languages; formal power series},

language = {eng},

month = {11},

number = {4},

pages = {479-493},

publisher = {EDP Sciences},

title = {Regularity of languages defined by formal series with isolated cut point∗},

url = {http://eudml.org/doc/277838},

volume = {46},

year = {2012},

}

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

DA - 2012/11//

PB - EDP Sciences

VL - 46

IS - 4

SP - 479

EP - 493

AB - 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.

LA - eng

KW - Formal power series; Hadamard quotient; regular languages; formal power series

UR - http://eudml.org/doc/277838

ER -

## References

top- M. Anselmo and A. Bertoni, On 2pfas and the Hadamard quotient of formal power series. Bull. Belg. Math. Soc.1 (1994) 165–173. Zbl0803.68073
- J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988). Zbl0668.68005
- 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. Zbl0327.94069
- 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. Zbl0366.94064
- 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. Zbl1037.68058
- V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst.36 (2003) 231–245. Zbl1039.68061
- V.D. Blondel, E. Jeandel, P. Koiran and N. Portier, Decidable and undecidable problems about quantum automata. SIAM J. Comput.34 (2005) 1464–1473 Zbl1078.81012
- A. Brodsky and N. Pippenger, Characterization of 1-way quantum finite automata. Available on . Zbl1051.68062URIhttp://xxx.lanl.gov/abs/quant-ph/9903014
- C. Choffrut, Private communication to the authors, July 2011.
- N. Chomsky and M.P. Schützenberger, The Algebraic Theory of Context-Free Languages, in Computer Programming and Formal Systems. North-Holland, Amsterdam (1963). Zbl0148.00804
- M. Droste, W. Kuich and H. Vogler, Handbook of weighted automata. EATCS Series Springer (2009). Zbl1200.68001
- C. Dwork and L. Stockmeyer, A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput.19 (1990) 1011–1023. Zbl0711.68075
- R. Freivalds, Probabilistic Two-way Machines, in Proc. of Int. Symp. Math. Found. Comput. Sci. Lect. Notes Comput. Sci.118 (1981) 33–45. Zbl0486.68045
- G. Jacob, La finitude des représentations linéaires des semigoupes est décidable. J. Algebra52 (1978) 437–459. Zbl0374.20074
- 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. Zbl0766.68098
- 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).
- A. Paz, Introduction to Probabilistic Automata. Academic Press (1971). Zbl0234.94055
- M. Rabin, Probabilistic automata. Inf. Control6 (1963) 230–245.
- A. Salomaa and M. Soittola, Automata-theoretic aspects of formal power series. Springer (1978). Zbl0377.68039
- M.P. Schützenberger, On the definition of a family of automata. Inf. Control4 (1961) 245–270. Zbl0104.00702
- 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. I306 (1988) 97–102.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.