On the Recognition of Primes by Automata

DOI10.1145/321466.321470zbMath0164.05201OpenAlexW2015619699WikidataQ59411176 ScholiaQ59411176MaRDI QIDQ5548359

Publication date: 1968

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/5864

zbMATH Keywords

number theory

Related Items (23)

How to prove that a sequence is not automatic ⋮ Two memory bounds for the recognition of primes by automata ⋮ Subset sum ``cubes and the complexity of primality testing ⋮ Two memory bounds for the recognition of primes by automata ⋮ Properties and limits of recognition of sets of integers by countable automata ⋮ (Non)Automaticity of number theoretic functions ⋮ Uniform tag sequences ⋮ Unnamed Item ⋮ Space complexity in on-line computation ⋮ Spanning trees: A survey ⋮ Automaticity. IV: Sequences, sets, and diversity ⋮ Functions Definable by Arithmetic Circuits ⋮ On a problem of Gelfond: the sum of digits of prime numbers ⋮ A lower bound for primality ⋮ A combinatorial ranking problem ⋮ Marker automata ⋮ A definition of measures over language space ⋮ On the complexity of a family of \(k\)-context-free sequences ⋮ Tree adjunct languages as integer set recognizers† ⋮ Matroid basis graphs. I ⋮ Absolutely parallel grammars and two-way finite-state transducers ⋮ Tape-reversal bounded Turing machine computations ⋮ Additive Number Theory via Approximation by Regular Languages

This page was built for publication: On the Recognition of Primes by Automata