The automata-theory tag has no wiki summary.

**1**

vote

**1**answer

73 views

### Relations between Arboreal Group Theory and Tree Group Actions?

By a tree group action, we mean an action of a group $G$ over the infinite regular binary tree $T_2$ such that for each $g \in G$, the mapping $x \rightarrow g.x$ is an automorphism of $T_2$; these ...

**0**

votes

**0**answers

83 views

### Free Groups and Automatic Structures [migrated]

I would like to know How can we prove that free groups are automatics? and is it possible to determine the number of states that would have a shortlext automatic structure (Word Acceptor and ...

**-4**

votes

**1**answer

67 views

### How do you prove that a subset of L is regular is L is regular? [closed]

I know that a regular language can be made into a DFA, so can I just make a DFA for the regular language? Also, someone told me I should make a e-NFA from the DFA, but I don't see what would be the ...

**3**

votes

**0**answers

101 views

### Computing the pro-solvable closure of a finitely generated subgroup of a free group

The pro-solvable topology on a group $G$ is the unique group topology such that the set of normal subgroups $N\lhd G$ with $G/N$ a finite solvable group is a fundamental system of neighborhoods of the ...

**6**

votes

**1**answer

115 views

### Separating infinite words sharing factors by automata

Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.
Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...

**0**

votes

**1**answer

94 views

### An extension of the real semiring with multiple degrees of infinity

Is it possible to define an extension of the probability semiring $(\mathbb{R}^+, +, \times, 0, 1)$ such that
Closure $a^* = 1 + a + a^2 + \ldots$ is defined for every element of the semiring, not ...

**5**

votes

**1**answer

69 views

### Generalising the adherence operator and its closure properties with regard to regular (rational) languages

Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some ...

**2**

votes

**1**answer

107 views

### Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)

Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$
the set of factors (consecutive finite subsequences) of length $n$ and consider the set
$$
K_n(\xi) = ...

**0**

votes

**0**answers

64 views

### Proof of conjecture that permutation-free automata restrict the possible states visitable from a stringset sharing prefixes and infixes

An automaton $\mathcal A = (X, Q, \delta, q_0)$ is called permutation-free iff no word $w \in X^*$ induces a nontrivial permutation of a subset of the states of $\mathcal A$. More formally for any $R ...

**3**

votes

**1**answer

96 views

### Subsets of $\omega$-regular lanuages accepted by automata with special acceptance condition

Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words:
The automata accepts $\xi \in X^{\omega}$ with respect to $F$ ...

**1**

vote

**1**answer

133 views

### Optimum control of a probabilistic automaton

Suppose we have a probabilistic automaton and we assign a weight to each state. An "interaction strategy" would be a fixed map from states to inputs. Any interaction strategy could be used to ...

**2**

votes

**1**answer

96 views

### Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular

Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages
$$
L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi ...

**2**

votes

**1**answer

64 views

### Varieties of rational languages and (pseudo-)varieties of finite monoids, question regarding closure property

Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff
...

**5**

votes

**2**answers

247 views

### Isomorphism in category of finite automata

What does meanthat two finite automata is equivalent? I think that we must define category of finite automata, i.e. we must define $\mathrm{Hom}(A,B)$, where $A,B$ be an arbitrary finite automata. ...

**1**

vote

**0**answers

154 views

### What is this structure called?

(I'm not entirely sure what to tag this; feel free to retag.)
While thinking about automata (specifics below), I ran into the following phenomenon:
A cofunction system is a pair of sets $X, A$, ...

**5**

votes

**1**answer

159 views

### Is it decidable whether the support of a rational $\mathbb{Z}$-series is a regular language?

Let $S \in \mathbb{Z}\langle\langle A\rangle\rangle$ be a rational series in noncommutative variables. The support of $S$ is the set of all words $u \in A^*$ such that $(S, u) \not= 0$. It is ...

**1**

vote

**0**answers

91 views

### Schönhage's SMM with only one instruction

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 hundred) instructions ...

**3**

votes

**2**answers

494 views

### Turing-complete primitive blind automata

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 all computable ...

**1**

vote

**1**answer

484 views

### Collatz conjecture— finite state machine transducer construction, origination?

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 computing sequential ...

**4**

votes

**0**answers

87 views

### Properties of classical automata preserved in Büchi automata

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 example: $L(A) ...

**2**

votes

**1**answer

324 views

### Let G and H be finite index subgroups of a free group. Does GH=HG?

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 true that $GH=HG$? ...

**7**

votes

**5**answers

446 views

### Generating function of a regular language

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 two polynomials ...

**0**

votes

**1**answer

256 views

### prove (a+b)*=a*(ba*)* [closed]

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

**4**

votes

**1**answer

424 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) ...

**4**

votes

**0**answers

176 views

### How should one generate a random set of mappings?

My motivation for this question comes from the study of synchronizing automata. There is a general consensus that random automata are synchronizing and have short synchronizing words. I am hoping ...

**3**

votes

**2**answers

851 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?

**5**

votes

**2**answers

569 views

### Rabin's Tree Theorem

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 two successor ...

**5**

votes

**0**answers

177 views

### Büchi automata with acceptance strategy

I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can always remove ...

**1**

vote

**2**answers

363 views

### Translate a buchi automaton to LTL

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 given any Buchi ...

**1**

vote

**1**answer

452 views

### example :concatenation of 2 undecidable language gives a decidable language [closed]

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

**0**

votes

**1**answer

241 views

### Universality of blind graph rewriting

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 nodes $M$, which has ...

**3**

votes

**1**answer

616 views

### Algebraic structure generated by primitive graph operations

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 exactly two arrows ...

**4**

votes

**0**answers

141 views

### connectivity in automata by words of length n-1

Let $A$ be a complete strongly connected automaton with $n$ states. Does always exist a word $v$ of length at most $n-1$ such that its underlying graph is connected?
That is for any pair of distinct ...

**2**

votes

**0**answers

310 views

### Question about $\omega$-regular languages

As most of you already know, in model checking most linear-time properties are either safety properties or liveness properties. A linear time property is usually described with an $\omega$-regular ...

**3**

votes

**2**answers

730 views

### Certain type of regular languages

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 characterisation, that ...

**11**

votes

**0**answers

185 views

### Eilenberg's rational hiererchy of nonrational automata & languages — where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...

**3**

votes

**2**answers

767 views

### Are context-free languages with context-free complements necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.
If $L$ and $L'$ are both context-free, are ...

**2**

votes

**1**answer

434 views

### Study of free monoids of the recursive S. Eilenberg.

Compared to the usual treatises on recursion (eg, Rogers H. "Computability and Undecidability." McGraw-Hill, New York) the book of Samuel Eilenberg & Calvin C. Elgot "Recursiveness" treats such ...

**7**

votes

**2**answers

540 views

### Can you hide a letter without losing information?

Consider the following game between Alice and Bob.
$\Sigma$ is a finite nonempty alphabet, $\Delta \notin \Sigma$ denotes
a special symbol, and $k > 0$ is a positive integer constant representing
...

**3**

votes

**3**answers

425 views

### Finite variation and idempotent languages and automata.

Let $L$ be a regular language over alphabet $\Sigma$ and let $A:=(Q,\Sigma,\delta, q_0, F)$ be the minimal DFA recognizing $L$. For every $w\in \Sigma^*$ define the variation of $w$ w.r.t. $L$ by
...

**0**

votes

**1**answer

441 views

### Transition Graph per alphabet?

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...

**4**

votes

**1**answer

315 views

### Growth zeta-functions of regular languages

Dear All,
my following question may be known and ought to be known, so in case it is folklore please could you give me the references.
To start, it is obvious that growth of rational languages are ...

**2**

votes

**1**answer

257 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 ...

**11**

votes

**1**answer

525 views

### Complementation of $\omega$-regular languages in reverse mathematics

Does anyone know where Büchi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over ...

**5**

votes

**2**answers

603 views

### A special class of regular languages: “circular” languages. Is it known?

We can define a subclass of the regular languages. Fix an alphabet $\Sigma$. Define the "circular" languages (actually, the name already exists to denote a different thing it seems, used in the field ...

**2**

votes

**3**answers

378 views

### 'Closure' of CFLs under complementation and intersection

Consider two context-free languages $L_1, L_2$. Of course, $L_1 - L_2, L_1\cap L_2, \bar{L}_1$, etc. are not necessarily context-free, but they are context-sensitive (the second is easy, the other two ...

**0**

votes

**1**answer

243 views

### A Nomenclature Issue : Imprimitive Semigroup?

The following question was asked by me on the forum sci.math.research,
“An imprimitive group is a transitive permutation group with a non-trivial
equivalence relation compatible with the action of ...

**7**

votes

**3**answers

887 views

### Wolfram's 2-state 3-symbol Turing machine

A few years ago it was announced that a 2-state symbol Turing machine was proven to be universal. However, Vaughn Pratt disputed the proof, and I gather he still disputes it. Wolfram's prize committee ...

**5**

votes

**0**answers

183 views

### “Question-answer” bisimulation

I often come across relations that would be defined as a bisimulation, except that the label match can be "inexact", that is, in the bisimulation game, a move labelled with "a" can be replied to with ...

**1**

vote

**1**answer

191 views

### Dumb question about Minimization in IATLC

I have probably a pretty dumb question about the classical Minimization algorithm for a DFA, as described in the Hopcroft book "Introduction to Automata Theory, Languages and Computation", pg. ...