Questions tagged [automata-theory]
The automata-theory tag has no summary.
110 questions
1 vote
0 answers
97 views
Reducing uniquely solvable linear Diophantine equation over naturals to fewer variables
This question is (well, barely!) motivated by automata theory, but maybe there is a pure number-theoretic perspective that I'm missing. In the following all variables range over $\mathbb N$. The ...
- 25.2k
0 votes
1 answer
166 views
On the behaviour of individual random walks of a Markov Chain
My current research (on Probabilistic Automaton) brought me to the following question regarding Markov Chains. I state the definitions for the sake of clarity. Let $M$ be a discrete-time finite Markov ...
3 votes
1 answer
231 views
Proof of dynamic programming calculation of Levenshtein distance
Let s1 and s2 are 2 arbitrary strings with lengths l1 and ...
- 213
2 votes
1 answer
229 views
Understanding Syntactic Congruence & Order
Reading through Jean-Eric Pin's "Mathematical Foundations of Automata Theory". Love this book. However, I am confused by the following section, and am hoping for some clarity and more ...
- 23
4 votes
2 answers
289 views
Given an automatic set $S$ coming from a DFA $M$ when read little-endian, is $\overline{d}(S)$ at most the Büchi acceptance probability of $M$?
Note: I've entirely rewritten this question! Originally it was just the third formulation, take note of that when reading answers. Let's say $S$ is a $b$-automatic set, and let's say $M$ is a DFA ...
- 2,825
0 votes
0 answers
102 views
A cellular automaton with an image that is not closed
Let $G$ be a non-locally finite periodic group and let $V$ be an infinite-dimensional vector space over a field $\mathbb{F}$. Does there exist a nontrivial topology on $V^G$ and a linear cellular ...
- 891
1 vote
1 answer
178 views
If a language $L$ is accepted by a non-deterministic automation, then $L$ is regular [closed]
The following lemma is from the book Discrete groups by Ohshika. If a language $L$ is accepted by a non-deterministic automaton, then $L$ is regular, i.e., there exists a finite state automaton $M$ ...
3 votes
1 answer
923 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 ...
- 73
-3 votes
1 answer
660 views
Counter net decidability [closed]
Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
- 73
7 votes
4 answers
1k 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 ...
- 211
2 votes
0 answers
104 views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
1 vote
0 answers
87 views
Does Frobenius number increase if bound on input increases?
The Frobenius number F is the largest number not expressible as a non-negative linear combination of some set of positive integers $\{a_i\}$, where, $a_i$ has gcd 1. Denote $maxF(n)$ as the maximum of ...
0 votes
0 answers
102 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 ...
- 489
4 votes
0 answers
208 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 ...
- 489
6 votes
0 answers
138 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 ...
- 489
2 votes
2 answers
184 views
A question on regular sets
In the end of the Abstract of the paper Minsky and Papert - Unrecognizable Sets of Numbers, the authors write "…for every infinite regular set $A$ there is a nonregular set $A'$ for which $$ \...
- 365
5 votes
1 answer
198 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?...
- 51
32 votes
2 answers
2k 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 ...
- 321
1 vote
1 answer
197 views
Shortest word accepted by a PDA
Given a pushdown automaton (PDA), we seek a shortest word accepted by it. A standard approach is to map the problem in the corresponding context-free grammar. Can we analyze and solve this problem ...
- 327
1 vote
0 answers
73 views
Effect on finite transformation semigroup under a particular modification of the generators
The following question arises in connection with problems in automata theory related to the road problem. Let $f_1, f_2: [N] \to [N]$ be maps such that the transformation semigroup $S = \langle f_1, ...
- 735
2 votes
0 answers
132 views
Name for the theory of words with equal length, prefix, successors
I've worked with this theory for a while, but I've never been quite sure what to call it: $$(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$$ Where $\Sigma^*$ is the set of finite words on finite ...
- 489
2 votes
1 answer
235 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,440
4 votes
1 answer
170 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 ...
- 41
1 vote
1 answer
255 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 ...
1 vote
0 answers
90 views
What a generating function for a language tells us about the language [closed]
What a generating function for a language tells us about the language .I need its answer in base of automata?
19 votes
2 answers
778 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,871
6 votes
1 answer
252 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 ...
- 63
0 votes
0 answers
46 views
Probabilistic timed automata transition
I am kind of new to timed automata and I have a question related to their correctness and synchronisation. Assume that I have three states, A, B and C. I have also two clocks, $x$ and $y$ that are ...
- 39
1 vote
1 answer
197 views
Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?
Recently, a student and I have been working through Waksman's paper ``An Optimum Solution to the Firing Squad Synchronization Problem.'' The paper claims that for any value of $n$, the proposed ...
- 413
2 votes
1 answer
115 views
For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset
Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state ...
- 798
2 votes
0 answers
123 views
Why can a least fixed point operator only be expanded finitely many times?
If we expand modal logic with least and greatest fix point operators $\mu$ and $\nu$, respectively, we obtain the logic $L_\mu$. An alternating automaton on infinite trees has a state space that is ...
- 21
1 vote
0 answers
394 views
Characterization of non-Zeno functions $f:\mathbb{R}\rightarrow \{0,1\}$
[Edit: I tried to integrate Nate's comments (see below).] In the context of automata over continuous time, consider Boolean-valued functions $f:\mathbb{R}\rightarrow \{0,1\}$. There are uncountably ...
- 9,934
1 vote
1 answer
141 views
Minimal DFA of L* [closed]
I'm learning how to minimize DFAs. Are the number of states in the minimal DFA of L, is equal to the number of states in the minimal DFA of L*? I'm trying for hours to think of examples but couldn't ...
3 votes
0 answers
274 views
Intersection of cone types
Let $G$ be a finitely generated hyperbolic group with the word metric; fix a symmetric generating set $S$ and let $\mathcal{G}$ be the Cayley graph of $G$ w.r.t. $S$. Define the cone of an element $x\...
- 329
2 votes
0 answers
94 views
If a timed automaton always terminates, does there exist a trace with a maximum length?
I have a theoretical question regarding timed automata and I would like to know if someone has already given an answer to it, since that would be useful for my research. So my question is the ...
1 vote
0 answers
300 views
What does homomorphism between languages mean to the correspoding Turing Machines?
According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the ...
- 3,296
11 votes
1 answer
366 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 ...
- 25.2k
3 votes
4 answers
2k 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 ...
- 1
0 votes
2 answers
299 views
Verification of Turing-equivalent automata
Correct me if I slept in my computer science studium: If an automaton is Turing-equivalent, the Halting problem shows that there are programs we can not verify (since we can't even predict their ...
- 4,859
2 votes
0 answers
326 views
Life. Intermediate stages
My question is pure mathematics when restricted to the cellular automata theory. John von Neumann got the grasp of and defined life. Many years later biologists supported von Neumann's definition of ...
- 7,600
5 votes
1 answer
523 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 ...
- 171
1 vote
1 answer
439 views
Modal logic in combination with automata theory
I'm planning to write a paper about the possibility of describing modal logic and the multiple world aspect of it with techniques of automata theory. To not duplicate my work does anyone have more ...
- 163
4 votes
1 answer
549 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 ...
- 9,934
5 votes
0 answers
269 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 ...
- 27.5k
1 vote
1 answer
212 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
5 votes
2 answers
616 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,...
- 61
1 vote
1 answer
3k 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 ...
- 4,859
-2 votes
1 answer
173 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 $...
- 59
-2 votes
1 answer
301 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 ...
- 7
2 votes
1 answer
302 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 ...
- 59