New Languages of Abstract Automata

EasyChair Preprint no. 7718

Abstract

The conventional theory of automata and algorithms associates only one language with each automaton or algorithm. Here it is demonstrated that each automaton or algorithm determines several algorithmic languages on different levels of computability. Properties of these languages and relations between them and conventional languages of automata or algorithms are studied. The obtained results made possible the discovery of a new class of algorithmic languages in addition to the well-known recursively enumerable and recursively coenumerable languages. The new languages are called recursively bienumerable comprising both recursively enumerable and recursively coenumerable languages.

Keyphrases: algorithmic language, finite automaton, logic, recursively coenumerable language, recursively enumerable language, Turing machine

@Booklet{EasyChair:7718,
  author = {Mark Burgin},
  title = {New Languages of Abstract Automata},
  howpublished = {EasyChair Preprint no. 7718},

  year = {EasyChair, 2022}}