Questions tagged [automata-theory]
The automata-theory tag has no usage guidance.
93
questions
0
votes
0answers
46 views
Partitions of a union of complete graphs into independent sets
Let $r,m,N,n \geq 1$ be integers with $r \leq N \leq rm$, $m \leq \binom{N}{r}$, and $n \leq \binom{N}{r} (N-r)^r$. These constraints are to prevent trivialities.
Let $V$ be a set with $|V| = N$, and ...
1
vote
0answers
48 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, ...
2
votes
0answers
75 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
1answer
101 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 ...
4
votes
1answer
111 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 ...
1
vote
1answer
134 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
0answers
68 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?
18
votes
2answers
569 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)...
6
votes
1answer
148 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 ...
0
votes
0answers
25 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 ...
1
vote
1answer
144 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 ...
2
votes
1answer
59 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 ...
2
votes
0answers
94 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 ...
1
vote
0answers
254 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
0answers
38 views
Sampling non-isomorphic Moore automata
Consider the set of Moore machines with input alphabet $A$, output alphabet $B$, and state set $S$. Let $\langle f, g \rangle$ be a machine with transition function $f : A \rightarrow S \rightarrow S$ ...
1
vote
1answer
87 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
0answers
121 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\...
2
votes
0answers
61 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
0answers
184 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 ...
11
votes
1answer
310 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 ...
3
votes
4answers
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 ...
0
votes
2answers
201 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 ...
1
vote
0answers
286 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 ...
5
votes
0answers
201 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 ...
1
vote
1answer
227 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 ...
4
votes
1answer
372 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 ...
5
votes
0answers
226 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 ...
2
votes
1answer
131 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 ...
5
votes
2answers
416 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,...
1
vote
1answer
2k 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 ...
-2
votes
1answer
121 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 $...
-2
votes
1answer
262 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
1answer
249 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 ...
4
votes
1answer
124 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 ...
2
votes
0answers
41 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 ...
5
votes
1answer
442 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
vote
1answer
223 views
The automorphism groups of smallest grammars of a language string are isomorphic
Let $s \in \Sigma^*$ be a formal language string. Consider the automorphism group of $s$, defined to be the set of all permutations of positions of $s$ that leave $s$ fixed. For instance $G(abab) = \...
3
votes
0answers
213 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,...
6
votes
2answers
522 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
0answers
219 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
1answer
245 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
1answer
186 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
0answers
55 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 ...
6
votes
0answers
521 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
1answer
151 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 ...
-1
votes
1answer
234 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 ...
7
votes
1answer
113 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-...
2
votes
1answer
136 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
0answers
140 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 \...
4
votes
1answer
157 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$ ...