Decidability questions related to abstract numeration systems

Honkala, Juha; Rigo, Michel

doi:10.1016/j.disc.2004.05.004

Request a copy

Article (Scientific journals)

Decidability questions related to abstract numeration systems

Honkala, Juha; Rigo, Michel

2004 • In Discrete Mathematics, 285 (1-3), p. 329-333

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/2283

DOI
10.1016/j.disc.2004.05.004

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

jhmr.pdf

Author preprint (187 kB)

Request a copy

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

numeration system; HD0L system; decidability

Abstract :

[en] We show that some decidability questions concerning recognizable sets of integers for abstract numeration systems are equivalent to classical problems related to HD0L systems. It turns out that these problems are decidable when the sets of representations of the integers are slender regular languages. (C) 2004 Elsevier B.V. All rights reserved.

Disciplines :

Mathematics

Author, co-author :

Honkala, Juha

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Decidability questions related to abstract numeration systems

Publication date :

06 August 2004

Journal title :

Discrete Mathematics

ISSN :

0012-365X

eISSN :

1872-681X

Publisher :

Elsevier Science Bv, Amsterdam, Netherlands

Volume :

285

Issue :

1-3

Pages :

329-333

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 10 December 2008

Statistics

Number of views

50 (1 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Allouche J.-P., Shallit J. Automatic Sequences: Theory, Applications, Generalizations. 2003;Cambridge University Press, Cambridge.
Berstel J., Reutenauer C. Rational Series and Their Languages. 1988;Springer, Berlin.
Bruyère V., Hansel G. Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181:1997;17-43.
Bruyère V., Hansel G., Michaux C., Villemaire R. Logic and. p -recognizable sets of integers Bull. Belg. Math. Soc. Simon Stevin. 1:1994;191-238.
Cobham A. Uniform tag sequences. Math. Systems Theory. 6:1972;164-192.
Honkala J. A decision method for the recognizability of sets defined by number systems. Theoret. Inform. Appl. 20:1986;395-403.
J. Honkala, It is decidable whether the image of an ℕ -rational sequence has a base, submitted for publication.
Honkala J., Ruohonen K. On the images of. ℕ -rational sequences counting multiplicities Internat. J. Algebra Comput. 13:2003;303-321.
Kari L., Rozenberg G., Salomaa A. L systems. Rozenberg G., Salomaa A. Handbook of Formal Languages. Vol. 1:1997;253-328 Springer, Berlin.
Lecomte P.B.A., Rigo M. Numeration systems on a regular language. Theory Comput. Syst. 34:2001;27-44.
Pǎun G., Salomaa A. Thin and slender languages. Discrete Appl. Math. 61:1995;257-270.
Rigo M. Generalization of automatic sequences for numeration systems on a regular language. Theoret. Comput. Sci. 244:2000;271-281.
Rigo M. Numeration systems on a regular language. arithmetic operations, recognizability and formal power series Theoret. Comput. Sci. 269:2001;469-498.
Rigo M., Maes A. More on generalized automatic sequences. J. Autom. Lang. Comb. 7:2002;351-376.
Shallit J. Numeration systems, linear recurrences and regular sets. Inform. and Comput. 113:1994;331-347.