The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
94 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 ...
11
votes
0answers
185 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 ...
5
votes
0answers
177 views

Büchi automata with acceptance strategy

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 always remove ...
5
votes
0answers
183 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 ...
4
votes
0answers
87 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
0answers
176 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
0answers
141 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
0answers
102 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 ...
2
votes
0answers
310 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 ...
1
vote
0answers
154 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
0answers
91 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
0answers
64 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 ...