Questions tagged [automata-theory]
The automata-theory tag has no usage guidance.
30
questions with no upvoted or accepted answers
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 ...
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 ...
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 ...
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 "...
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 ...
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 ...
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) \...
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 ...
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 ...
3
votes
0
answers
201
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\...
3
votes
0
answers
222
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,...
3
votes
0
answers
864
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 ...
2
votes
0
answers
53
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 ...
2
votes
0
answers
98
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 ...
2
votes
0
answers
102
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 ...
2
votes
0
answers
65
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 ...
2
votes
0
answers
46
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 ...
1
vote
0
answers
63
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 ...
1
vote
0
answers
55
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, ...
1
vote
0
answers
261
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 ...
1
vote
0
answers
251
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 ...
1
vote
0
answers
295
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 ...
1
vote
0
answers
58
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 ...
1
vote
0
answers
228
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$, ...
1
vote
0
answers
108
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 ...
0
votes
0
answers
64
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 ...
0
votes
0
answers
58
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 ...
0
votes
0
answers
28
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 ...
0
votes
0
answers
152
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 \...
-1
votes
1
answer
247
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 ...