On the Recognition of Primes by Automata

DOI10.1145/321466.321470zbMATH Open0164.05201OpenAlexW2015619699WikidataQ59411176 ScholiaQ59411176MaRDI QIDQ5548359FDOQ5548359

Authors: Herbert S. Shank, J. Hartmanis 

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

Cited In (23)

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

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

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