Questions tagged [automata-theory]
The automata-theory tag has no usage guidance.
109 questions
2
votes
0
answers
47
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 ...
- 21
6
votes
1
answer
563
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-...
- 61
1
vote
1
answer
260
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) = \...
- 260
3
votes
0
answers
223
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,...
- 186
6
votes
2
answers
647
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 ...
- 370
1
vote
0
answers
230
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 ...
- 11
3
votes
1
answer
275
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}, \...
- 73
2
votes
1
answer
208
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 ...
- 125
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 ...
- 3,084
6
votes
0
answers
572
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 ...
- 38.6k
6
votes
1
answer
165
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 ...
- 798
-1
votes
1
answer
249
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 ...
6
votes
1
answer
135
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-...
- 798
2
votes
1
answer
143
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[...
- 798
0
votes
0
answers
154
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 \...
- 798
4
votes
1
answer
172
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$ ...
- 798
1
vote
1
answer
160
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 ...
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 ...
- 798
2
votes
1
answer
197
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
...
- 798
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. ...
- 203
1
vote
0
answers
230
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$, ...
- 21.1k
4
votes
1
answer
322
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 ...
- 841
1
vote
0
answers
111
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 ...
3
votes
2
answers
790
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 ...
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 ...
- 529
4
votes
0
answers
125
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) \...
- 73
1
vote
1
answer
404
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$? ...
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(...
user6976
-1
votes
1
answer
7k
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
- 9
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) =...
- 105
4
votes
0
answers
216
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 ...
- 38.6k
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?
- 73
5
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 ...
5
votes
0
answers
326
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 ...
- 1,341
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 ...
- 73
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.
- 21
2
votes
1
answer
286
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 ...
4
votes
1
answer
967
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
154
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
893
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 ...
- 173
3
votes
2
answers
776
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 ...
- 1,437
13
votes
0
answers
274
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 ...
- 161
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 ...
- 387
3
votes
1
answer
528
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 ...
- 4,165
7
votes
2
answers
622
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
...
- 73
3
votes
3
answers
552
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
$$\...
- 424
-1
votes
1
answer
1k
views
Transition Graph per alphabet? [closed]
How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
- 101
6
votes
1
answer
516
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 ...
- 1,437
2
votes
1
answer
435
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 ...
- 143
12
votes
3
answers
877
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 $\...
- 866