All Questions
Tagged with automata-theory computability-theory
8 questions
0
votes
0
answers
66
views
First-order logics expressively equivalent to the computable languages
There is a really nice theorem that the subsets of $(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$ definable in first-order logic are exactly the regular sets.
Where:
$\Sigma^*$ is the set of ...
- 429
2
votes
1
answer
168
views
Busy beaver sequence for a simple tag-like system
This question arose in the context of tag-like systems, specifically Bitwise Cyclic Tag (BCT). Consider the following discrete dynamical system:
Let $\mathbb{B} = \{\mathtt{0}, \mathtt{1}\}$. Let our ...
- 2,203
1
vote
1
answer
199
views
decidability of regularity of a language depending on representation
It is well known that many decision problems for regular languages are decidable. However, the proofs seem to rely on a witness of the regularity of said language, be it an automaton, a grammar, a ...
18
votes
2
answers
708
views
Is Post's tag system solved?
Has the 3-tag system investigated by Emil Post $(0\to00, 1\to1101)$ been solved? Is there a decision algorithm to determine which starting strings terminate, which end up in a cycle, and which (if any)...
- 2,811
1
vote
1
answer
183
views
Understanding the paper: "Guarded Fixed Point Logic"
This question is specifically about the paper "Guarded Fixed Point Logic" by Gradel and Walukiewicz. Among other things they prove the decidability of the satisfiability problem for Fixpoint Loosely ...
- 111
4
votes
1
answer
2k
views
Deciding equivalence of regular languages
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) = L(M_R)$ and $L(S) =...
- 105
7
votes
3
answers
3k
views
Is there an algorithm that can "reverse engineer" a Regular Expression?
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 that language?
- 73
2
votes
1
answer
435
views
Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)
Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
- 143