The automata-theory tag has no usage guidance.

**4**

votes

**2**answers

130 views

### Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...

**6**

votes

**2**answers

315 views

### Deterministic finite-state automaton driven by a Markov chain

I've stumbled on some problem, and I have the feeling that this is closed to something well-studied in dynamical systems. The problem is the following. Consider a finite-state automaton with state ...

**1**

vote

**1**answer

191 views

### Non-regular languages fulfilling the Pumping Lemma

Some non-regular languages don't yield to the Pumping Lemma ($L_1=a^nb^mc^m$ should work). But now consider the set of non-regular languages L only over the alphabet {a}. (Like $L_2=a^{n^2}$ or ...

**-1**

votes

**1**answer

879 views

### Transition Graph per alphabet? [closed]

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

**12**

votes

**2**answers

634 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 $\...

**-2**

votes

**1**answer

101 views

### How one can use a real math function on transaction in Hybrid Petri Net fundamental equation?

Say we have a simple HPN with 2 continuous places $A$ and $B$ and one transition. We want a transition not only add and substract $N$ marks from $A$ and add $M$ to $B$ but use mathematical function $...

**5**

votes

**2**answers

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

**-2**

votes

**1**answer

91 views

### Deterministic Finite Automata question [closed]

I am very new to finite automata, and I came across an issue in my professors lecture slides which I think is wrong, and I'd wonder if any of you could confirm:
Alphabet: {1}
Automata
Surely the ...

**2**

votes

**1**answer

105 views

### How does “inhibitor arc” fit into fundamental equation of Hybrid Petri Nets?

In "ON HYBRID PETRI NETS" by DAVID AND ALLA published in 2001 on page 26 is given an example of how fundamental equation solves a HPN for given start and end time values.
A system looks like
And ...

**1**

vote

**0**answers

33 views

### Relation between indexed languages (OI-macro or context-free tree) and scattered context languages

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...

**4**

votes

**1**answer

102 views

### Computations with conetypes of hyperbolic groups

I'd like to know if there exists (and, in this case, where I can find it) some computer program/programming language/any kind of software that can find explicitly the conetypes of a hyperbolic group ...

**3**

votes

**0**answers

147 views

### Estimating the growth rate of nondeterministic finite automata

Given a nondeterministic finite automaton $\mathcal{A}$ (or a regular expression, or a regular grammar), can we efficiently compute the number $|L_k(\mathcal{A})|$ of accepted words of length $k$?
No,...

**5**

votes

**1**answer

185 views

### K-fellow traveler property and automatic structure

I have been reading several articles about automatic groups and metric spaces of negative curvature. However it is not clear for me the relationship between automatic groups, hyperbolcity and the k-...

**-1**

votes

**1**answer

206 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

**0**answers

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

**1**

vote

**0**answers

137 views

### LTL - Büchi-automaton Translation [closed]

I need some help in Generalized Büchi automaton ..
I do understand the translation of a LTL-formula ϕ into Generalized Büchi automaton A= (Q, Δ, I, F), with F= {F1,...,Fn}
My problem is F ..
I know ...

**3**

votes

**1**answer

167 views

### Exponential objects in a category of abstract automata

I'm working with a more or less standard definition of the category Aut(C) of automata over a category C (where C has finite products) which has tuples $$
A=\langle I_{A},O_{A},S_{A},\sigma_{A}, \...

**2**

votes

**1**answer

163 views

### QBF of exponential length?

We consider a slightly extended version of a nondeterministic finite automaton, call it a "propositional nondeterministic finite automaton". It is defined as follows. Consider a fixed propositional ...

**1**

vote

**0**answers

46 views

### Question about link between non-terminals of grammars and variables of Diophantine equations

If we change the right arrow in the rewriting rules of grammar into equators , changes all terminals into x and keep the non-terminals unchanged,we get system of equations.In some cases,those ...

**2**

votes

**0**answers

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

**6**

votes

**1**answer

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

**-4**

votes

**1**answer

1k 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 ...

**6**

votes

**1**answer

101 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 Büchi-...

**1**

vote

**1**answer

143 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

128 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) = \xi[...

**0**

votes

**0**answers

102 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

130 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$ ...

**2**

votes

**1**answer

249 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

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

**1**

vote

**0**answers

184 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

**2**answers

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

**5**

votes

**1**answer

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

**7**

votes

**6**answers

2k views

### Regular languages and the pumping lemma

In certain dark corners of computer science and group theory, one often wants to prove that a language is not a regular language (ie a language accepted by a finite state automaton).
The only ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

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

**5**

votes

**2**answers

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

**1**

vote

**0**answers

98 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

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

**0**

votes

**1**answer

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

**4**

votes

**0**answers

104 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

353 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

1k 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 $P(...

**3**

votes

**1**answer

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

**3**

votes

**2**answers

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

**-1**

votes

**1**answer

347 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

1k 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) ...

**3**

votes

**5**answers

1k views

### Theory mainly concerned with $\lambda$-calculus?

Automata theory is mainly concerned with Turing machines and all its relatives-in-spirit. $\lambda$-calculus is rather rarely mentioned in textbooks on automata theory.
What's the common name of the ...

**4**

votes

**0**answers

194 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

1k 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

**0**answers

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