On Sequences Defined by D0L Power Series

Juha Honkala

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 33, Issue: 2, page 125-132
  • ISSN: 0988-3754

Abstract

top
We study D0L power series over commutative semirings. We show that a sequence (cn)n≥0 of nonzero elements of a field A is the coefficient sequence of a D0L power series if and only if there exist a positive integer k and integers βi for 1 ≤ i ≤ k such that c n + k = c n + k - 1 β 1 c n + k - 2 β 2 ... c n β k for all n ≥ 0. As a consequence we solve the equivalence problem of D0L power series over computable fields.

How to cite

top

Honkala, Juha. "On Sequences Defined by D0L Power Series." RAIRO - Theoretical Informatics and Applications 33.2 (2010): 125-132. <http://eudml.org/doc/221981>.

@article{Honkala2010,
abstract = { We study D0L power series over commutative semirings. We show that a sequence (cn)n≥0 of nonzero elements of a field A is the coefficient sequence of a D0L power series if and only if there exist a positive integer k and integers βi for 1 ≤ i ≤ k such that $c_\{n+k\}=c_\{n+k-1\}^\{\beta_1\}c_\{n+k-2\}^\{\beta_2\}\ldots c_n^\{\beta_k\}$ for all n ≥ 0. As a consequence we solve the equivalence problem of D0L power series over computable fields. },
author = {Honkala, Juha},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {D0L system; D0L power series.; D0L power series},
language = {eng},
month = {3},
number = {2},
pages = {125-132},
publisher = {EDP Sciences},
title = {On Sequences Defined by D0L Power Series},
url = {http://eudml.org/doc/221981},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Honkala, Juha
TI - On Sequences Defined by D0L Power Series
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 2
SP - 125
EP - 132
AB - We study D0L power series over commutative semirings. We show that a sequence (cn)n≥0 of nonzero elements of a field A is the coefficient sequence of a D0L power series if and only if there exist a positive integer k and integers βi for 1 ≤ i ≤ k such that $c_{n+k}=c_{n+k-1}^{\beta_1}c_{n+k-2}^{\beta_2}\ldots c_n^{\beta_k}$ for all n ≥ 0. As a consequence we solve the equivalence problem of D0L power series over computable fields.
LA - eng
KW - D0L system; D0L power series.; D0L power series
UR - http://eudml.org/doc/221981
ER -

References

top
  1. J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer, Berlin (1988).  
  2. J. Honkala, On morphically generated formal power series. RAIRO, Theoret. Informatics Appl.29 (1995) 105-127.  
  3. J. Honkala, On the decidability of some equivalence problems for L algebraic series. Intern. J. Algebra and Comput.7 (1997) 339-351.  
  4. J. Honkala, On D0L power series, Theoret. Comput. Sci., to appear.  
  5. W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer, Berlin (1986).  
  6. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980).  
  7. G. Rozenberg and A. Salomaa, Eds., Handbook of Formal Languages 1-3. Springer, Berlin (1997).  
  8. A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer, Berlin (1978).  

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.