It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hun …

Let $N$ be the set of natural numbers, $S$ be the set of finite binary sequences, and $Q = [N \rightarrow N] \times [N \rightarrow N],$ where $[N \rightarrow N]$ is the set of al …

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer co …

It is well known that the generating function of a regular language $L$, i.e. $\sum n_kz^k$ where $n_k$ is the number of words of length $k$ in $L$, is rational, i.e. a quotient of …

Let $\Sigma$ be a finite set. Let $F_\Sigma$ be the free group over $\Sigma$. Let $G$ and $H$ be finite index subgroups of $F_\Sigma$. Consider the sets $GH$ and $HG$. Is it always …

Given two NFW $A$ and $B$, we regarded $A$ and $B$ as Büchi automata. We can show that the containment property is not preserved in Büchi automata. That is, we can construct a exa …

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed graph with the set of node …

formal language and automata theory regular expessions (a+b)* =a*(ba*)* please answer I want the proof thank you

Let $M$ be a finite set, and $S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$. Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has e …

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) …

Dear All, there is one type of regular languages, over ${a,b}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characte …

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces t …

How can I translate a Büchi automaton A to LTL(linear temporal logic) if $L(A)$ is definable in the LTL? MY idea is : Büchi automaton $A$ ===> QPTL ===> LTL I know that give …

give example of 2 languages A and B such that A and B are undecidable but there concatenation A.B is decidable.

I've been reading Rabin's article on decidability in Barwise's text, and I came across Rabin's discussion of the decidability proof of his tree theory: the second-order theory with …