Questions tagged [automata-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
31 votes
2 answers
1k views

Group theory with grep?

While reading Bill Thurston's obituary in the Notices of the AMS I came across the following fascinating anecdote (pg. 32): Bill’s enthusiasm during the early stages of mathematical discovery was ...
asama's user avatar
  • 311
27 votes
1 answer
1k views

Automatic groups - recent progress

Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental ...
Michal Kotowski's user avatar
18 votes
2 answers
694 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)...
Thomas's user avatar
  • 2,691
13 votes
3 answers
856 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 $\...
Alex Simpson's user avatar
12 votes
5 answers
3k 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(...
user avatar
12 votes
0 answers
268 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 ...
David Lewis's user avatar
11 votes
6 answers
3k views

Regular languages and the pumping lemma

Let's say that I want to prove that a language is not regular. The only general technique I know for doing this is the so-called "pumping lemma", which says that if $L$ is a regular language, then ...
Andy Putman's user avatar
  • 43.3k
11 votes
1 answer
323 views

Unique words in dihedral groups

Suppose $x$ is a word over the alphabet $\{0,1\}$. Let $a$, $b$ be elements of the group Dih$_k$ for some $k$. Let $\varphi=\varphi_{a,b,k}$ be the map from words over $\{0,1\}$ to elements of the ...
Bjørn Kjos-Hanssen's user avatar
8 votes
2 answers
2k 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. ...
St.Antario's user avatar
8 votes
3 answers
2k 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 ...
k2forever's user avatar
  • 381
8 votes
2 answers
919 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 ...
vincenzoml's user avatar
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?
Golan's user avatar
  • 73
7 votes
4 answers
923 views

Origin of tropical mathematics

On Wikipedia, it is claimed without a source that Imre Simon founded tropical mathematics. The first work of his I was able to find on the subject is Limited subsets of a free monoid which uses the ...
Oussema's user avatar
  • 211
7 votes
2 answers
617 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 ...
Cerno's user avatar
  • 73
7 votes
1 answer
129 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-...
StefanH's user avatar
  • 798
6 votes
2 answers
1k 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 ...
Daniel Osterman's user avatar
6 votes
1 answer
503 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 ...
Victor's user avatar
  • 1,427
6 votes
1 answer
523 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-...
Miguel's user avatar
  • 61
6 votes
1 answer
181 views

Embedding Turing machine [closed]

I have some questions about Turing machines. Is there an embedding method where you embed Turing machines, finite automata into continuous space or graphs? Or are there geometrical approaches to ...
vvv's user avatar
  • 63
6 votes
2 answers
586 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 ...
Peva Blanchard's user avatar
6 votes
1 answer
161 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 ...
StefanH's user avatar
  • 798
6 votes
0 answers
111 views

Are "germ" automata studied?

I've been exploring the idea of a nondeterministic continuous automaton based on germs: Two functions $f,g: \mathbb{R} \to S$ have the same right germ at $x$ if there is some interval $[x,a)$ on which ...
TomKern's user avatar
  • 429
6 votes
0 answers
554 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 ...
Benjamin Steinberg's user avatar
6 votes
0 answers
249 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 "...
vincenzoml's user avatar
5 votes
1 answer
143 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 ...
EM90's user avatar
  • 329
5 votes
1 answer
304 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 ...
J.-E. Pin's user avatar
  • 851
5 votes
2 answers
531 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,...
Distance's user avatar
5 votes
1 answer
381 views

Rabin's proofs of emptiness and complementation problems for automata on infinite trees

I have originally asked this question on Math.SE, but I think it is more suitable here. I have been reading M. Rabin's 1969 article Decidability of Second-Order Theories and Automata on Infinite ...
konewka's user avatar
  • 171
5 votes
0 answers
237 views

A problem on automatic groups and geodesic paths on the Cayley graph

Let $\Gamma = \langle S \mid R \rangle$ be a finitely generated group, with the neutral element $e \not \in S= S^{-1}$. Let $\ell : \Gamma \to \mathbb{N}$ be the world length related to $S$. For ...
Sebastien Palcoux's user avatar
5 votes
0 answers
319 views

Büchi automata with acceptance strategy [closed]

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 ...
Denis's user avatar
  • 1,291
4 votes
2 answers
2k 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 ...
Nick Loughlin's user avatar
4 votes
1 answer
121 views

Multi-head two-way finite automata versus logarithmic space

It is known that the languages decided by logarithmic-space Turing machines are exactly those decided by finite automata with multiple, bidirectional (2-way) scanning heads. Where could I find a proof?...
Matt's user avatar
  • 41
4 votes
1 answer
416 views

Giving the same concept different names in the same paper

I found a seminal paper of renowned authors (Inference of Finite Automata Using Homing Sequences (1993) by Ron Rivest and Robert Schapire) in which the authors define the very same set-theoretic ...
Hans-Peter Stricker's user avatar
4 votes
1 answer
165 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$ ...
StefanH's user avatar
  • 798
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) =...
Alberto's user avatar
  • 105
4 votes
1 answer
128 views

Can one reduce to 'reversing' the right multiplier finite-state automata of an automatic group to obtain a biautomatic structure?

Let $\left( G, A, W, \left\{ R_{a} \right\}_{a \in A \cup \{ 1 \}} \right)$ be a group equipped with an automatic structure, where $G$ is the group, $A$ is a finite set of generators of $G$, $W$ is ...
user171576's user avatar
4 votes
1 answer
964 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
155 views

Corollaries of Kleene's Theorem (Regular Languages)

Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the ...
TomKern's user avatar
  • 429
4 votes
0 answers
124 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) \...
LimaoLogic's user avatar
4 votes
0 answers
215 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 ...
Benjamin Steinberg's user avatar
4 votes
0 answers
153 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 ...
Mikhail Berlinkov's user avatar
3 votes
4 answers
1k views

Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?

There is a claim on https://en.wikipedia.org/wiki/Super-recursive_algorithm#Inductive_Turing_machines that 'Simple inductive Turing machines are equivalent to other models of computation such as ...
Turbo's user avatar
  • 13.6k
3 votes
5 answers
2k 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 ...
Hans-Peter Stricker's user avatar
3 votes
1 answer
1k 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 ...
vzn's user avatar
  • 529
3 votes
3 answers
545 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 $$\...
Xorwell's user avatar
  • 434
3 votes
3 answers
901 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 ...
alpoge's user avatar
  • 793
3 votes
1 answer
773 views

Language equivalence between deterministic and non-deterministic counter net

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
Lionheart's user avatar
3 votes
1 answer
517 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 ...
Buschi Sergio's user avatar
3 votes
1 answer
264 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}, \...
user130569's user avatar
3 votes
2 answers
783 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 ...