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

Abstract

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

How to cite

top

Bertoni, 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
  1. M. Anselmo and A. Bertoni, On 2pfas and the Hadamard quotient of formal power series. Bull. Belg. Math. Soc.1 (1994) 165–173.  
  2. J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988).  
  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.  
  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.  
  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.  
  6. V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst.36 (2003) 231–245.  
  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 
  8. A. Brodsky and N. Pippenger, Characterization of 1-way quantum finite automata. Available on .  URIhttp://xxx.lanl.gov/abs/quant-ph/9903014
  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).  
  11. M. Droste, W. Kuich and H. Vogler, Handbook of weighted automata. EATCS Series Springer (2009).  
  12. C. Dwork and L. Stockmeyer, A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput.19 (1990) 1011–1023.  
  13. R. Freivalds, Probabilistic Two-way Machines, in Proc. of Int. Symp. Math. Found. Comput. Sci. Lect. Notes Comput. Sci.118 (1981) 33–45.  
  14. G. Jacob, La finitude des représentations linéaires des semigoupes est décidable. J. Algebra52 (1978) 437–459.  
  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.  
  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).  
  18. M. Rabin, Probabilistic automata. Inf. Control6 (1963) 230–245.  
  19. A. Salomaa and M. Soittola, Automata-theoretic aspects of formal power series. Springer (1978).  
  20. M.P. Schützenberger, On the definition of a family of automata. Inf. Control4 (1961) 245–270.  
  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. I306 (1988) 97–102.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.