Characterizing simpler recognizable sets of integers

Rigo, Michel

doi:10.1007/3-540-45687-2_51

Request a copy

Paper published in a journal (Scientific congresses and symposiums)

Characterizing simpler recognizable sets of integers

Rigo, Michel

2002 • In Lecture Notes in Computer Science, 2420, p. 615-624

Peer reviewed

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

DOI
10.1007/3-540-45687-2_51

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

W16-final.pdf

Author preprint (203.43 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 :

Star-free languages; numeration systems; first-order logic

Abstract :

[en] For the k-ary numeration system, we characterize the sets of integers such that the corresponding representations make up a star-free regular language. This result can be transposed to some linear numeration systems built upon a Pisot number like the Fibonacci system and also to k-adic numeration systems. Moreover we study the problem of the base dependence of this property and obtain results which are related to Cobham's Theorem.

Disciplines :

Computer science

Author, co-author :

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

Language :

English

Title :

Characterizing simpler recognizable sets of integers

Publication date :

2002

Event name :

27th International Symposium : Mathematical Foundations of Computer Science

Event place :

Warsaw, Poland

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Special issue title :

27th International Symposium: Mathematical Foundations of Computer Science

Volume :

2420

Pages :

615-624

Peer reviewed :

Peer reviewed

Commentary :

The original publication is available at www.springerlink.com

Available on ORBi :

since 10 December 2008

Statistics

Number of views

66 (6 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

V. Bruyère, G. Hansel, Bertrand numeration systems and recognizability. Latin American Theoretical INformatics (Valparaíso, 1995). Theoret. Comput. Sci. 181 (1997), 17–43.
V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers. Journées Montoises (Mons, 1992). Bull. Belg. Math. Soc. Simon Stevin 1 (1994), 191–238.
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969)186–192.
S. Eilenberg, Automata, languages, and machines. Vol. A. Pure and Applied Mathematics, Vol. 58. Academic Press, New York, (1974).
A. S. Fraenkel, Systems of numeration. Amer. Math. Monthlys 92 (1985), 105–114.
C. Frougny, Representations of numbers and finite automata. Math. Systems Theory 25 (1992), 37–60.
L. Kari, G. Rozenberg, A. Salomaa, L systems. in Handbook of formal languages, Vol. 1, 253–328, Springer, Berlin, (1997).
A. de Luca, A. Restivo, Representations of integers and laguage theory, Mathematical foundations of computer science (Prague, 1984), 407–415, Lecture Notes in Comput. Sci. 176, Springer, Berlin, (1984).
A. de Luca, A. Restivo, Star-free sets of integers. Theoret. Comput. Sci. 43 (1986), 265–275.
R. McNaughton, S. Papert, Counter-free automata. M.I.T. Research Monograph, No. 65. The M.I.T. Press, Cambridge, Mass.-London, (1971).
A. Salomaa, Formal languages. Academic Press, New York, (1973).
M. P. Schützenberger, On finite monoids having only trivial subgroups. Information and Control 8 (1965), 190-194.
W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982), 360–376.