Questions tagged [automata-theory]
The automata-theory tag has no usage guidance.
105
questions
3
votes
2
answers
772
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 ...
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
2
answers
139
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
$$ \...
2
votes
1
answer
1k
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
193
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
...
2
votes
1
answer
157
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
votes
1
answer
69
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
1
answer
161
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 ...
2
votes
1
answer
274
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 ...
2
votes
1
answer
141
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[...
2
votes
1
answer
283
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 ...
2
votes
1
answer
204
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 ...
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 ...
2
votes
1
answer
414
views
Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)
Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
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 ...
1
vote
1
answer
248
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) = \...
1
vote
2
answers
2k
views
Translate a buchi automaton to LTL
How can I translate a Büchi automaton A to LTL(linear temporal logic) if $L(A)$ is definable in the LTL?
MY idea is : Büchi automaton $A$ ===> QPTL ===> LTL
I know that given any Buchi ...
1
vote
1
answer
2k
views
example :concatenation of 2 undecidable language gives a decidable language [closed]
give example of 2 languages A and B such that A and B are undecidable but there concatenation A.B is decidable.
1
vote
1
answer
82
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$ ...
1
vote
1
answer
395
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$? ...
1
vote
1
answer
151
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 ...
1
vote
1
answer
179
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
1
answer
155
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 ...
1
vote
1
answer
108
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 ...
1
vote
1
answer
344
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 ...
1
vote
1
answer
158
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 ...
1
vote
1
answer
242
views
Dumb question about Minimization in IATLC
I have probably a pretty dumb question about the classical Minimization algorithm for a DFA, as described in the Hopcroft book "Introduction to Automata Theory, Languages and Computation", pg. 155-164....
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
73
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?
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
228
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 ...
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
2
answers
236
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 ...
0
votes
1
answer
285
views
A Nomenclature Issue : Imprimitive Semigroup?
The following question was asked by me on the forum sci.math.research,
“An imprimitive group is a transitive permutation group with a non-trivial
equivalence relation compatible with the action of ...
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
6k
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