Characterizing simpler recognizable sets of integers

DOI10.1023/B:STUD.0000032105.17770.38MaRDI QIDQ1826937zbMATH OpenOpenAlexFDO

Authors Michel Rigo

Publication date 6 August 2004

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/b:stud.0000032105.17770.38

zbMATH Keywords

logical characterizationsnumeration systemsrecognizable sets of integersstar-free languages

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Theory of numerations, effectively presented structures (03D45)

Review text

The paper contributes to the area of characterizing recognizable sets of integers. One of the sources for the work was the well-known result by Mc Naughton and Papert which characterizes star-free languages (a proper subclass of regular languages) as those expressible in the first-order theory of linear order. Here the author considers sets of (nonnegative) integers as languages, containing representations of the integers in a (linear) numeration system (which includes the usual \(k\)-base systems or the Fibonacci system). A set of numbers \(X\) is \(U\)-recognizable (\(U\) being a numeration system) if the set of \(U\)-representations of elements of \(X\) is regular. The author recalls a nice result by Bruyere and Hansel showing that \(U\)-recognizability coincides with \(U\)-definability, for a certain class of numeration systems \(U\) (where the characteristic polynomial is the minimal polynomial of a Pisot number). Inspired by the mentioned sources, the author concentrates on star-free sets, and develops special logics \({\mathcal L}_{k,n}\), which characterize when a given set \(X\) is \(k\)-star-free (i.e., w.r.t. the integer base \(k\)). He then generalizes the obtained result for the above mentioned class of ``Pisot number numeration systems. Further results are given for \(k\)-ary systems (in particular, the base dependence question is studied) and for \(k\)-adic systems.

Recommendations

• scientific article; zbMATH DE number 1929973
• scientific article; zbMATH DE number 3936540
• Bertrand numeration systems and recognizability
• Recognizable sets of numbers in nonstandard bases
• Multi-dimensional sets recognizable in all abstract numeration systems

Cited in

(7)

• On recognizable sets of integers
• scientific article; zbMATH DE number 3936540 (Why is no real title available?)
• First-order logic and numeration systems
• scientific article; zbMATH DE number 1929973 (Why is no real title available?)
• scientific article; zbMATH DE number 3993564 (Why is no real title available?)
• Recognizable sets of numbers in nonstandard bases
• On \(\frac{p}{q}\)-recognisable sets

This page was built for publication: Characterizing simpler recognizable sets of integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1826937)