Automaatsetele

Automaatsetele is een term uit de theoretische informatica en getaltheorie die verwijst naar verzamelingen van natuurlijke getallen die door een eindige automaat kunnen worden herkend wanneer elk getal wordt gerepresenteerd in een vaste basis b ≥ 2. Een dergelijke verzameling wordt vaak aangeduid als een b-automatische verzameling.

Formeel: voor een vaste basis b ≥ 2 is een verzameling A ⊆ N b-automatisch als er een deterministische eindige automaat M bestaat die de base-b representaties van n accepteert precies wanneer n ∈ A. De representaties worden doorgaans gelezen van meest significante naar minst significante cijfer. De automaat kan dus in één pannenkoekoperatie bepalen of een getal tot de verzameling behoort op basis van de tekenreeks van zijn base-b notatie.

Eigenschappen: De klasse van b-automatische verzamelingen is dicht onder vereniging, doorsnede en complement. De theorie bevat centrale resultaten zoals dat de automaatsets stabiel blijven onder veelvoudige bewerkingen die binnen reguliere talen en logische definities voorkomen. Cobham’s stelling geeft onder bepaalde omstandigheden restricties tussen basis afhankelijkheden: als een verzameling automatisch is in twee multiplicatief onafhankelijke bases, dan is deze verzameling uiteindelijk periodiek.

Voorbeelden: De verzameling van even getallen is in elke basis b-automatisch. Een ander voorbeeld is de verzameling van getallen waarvoor de som van de cijfers even is; dit kan worden herkend door een eindige automaat die de verwerking van cijfers bijhoudt.

Toepassingen: automaatsetele komen voor in de studie van regelmatige talen gekoppeld aan getalrepresentaties, in modelchecking en in theoretische analyse van getalfuncties en -reeksen.

Zie ook: automatische reeksen, eindige automaat, formele talen, base-b representatie, Cobham’s theorem.