Questions tagged [omega-language]
Questions about ω-languages, i.e. about sets of infinite-length sequences of symbols. Typical examples include ω-regular languages or languages accepted by deterministic Büchi automata. The tag can also be used for questions about languates over ω-trees.
20
questions
7
votes
2
answers
153
views
Algebraic characterisation of star-free safety languages
It is known that star-free languages are definable by aperiodic syntactic monoids.
But is there any algebraic characterisation of star-free safety $\omega$-languages?
Edit: A language $L$ is safety if ...
- 1,416
3
votes
1
answer
194
views
Maximally Permissive Strategies for Safety Properties
Different definitions of maximally permissive strategies exist. For instance, in (Bernet, Janin, and Walukiewicz 2002), strategies are compared by looking at inclusion of the behaviors/outcomes they ...
- 349
2
votes
0
answers
92
views
Necessary and sufficient condition for an infinite tree to be context-free
A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
- 193
1
vote
1
answer
82
views
Definition of Rabin acceptance condition for omega automatons [closed]
I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left ...
- 111
4
votes
1
answer
241
views
Decomposition of safety and liveness properties
In Alpern,Schneider 86 is described how to extract the automata that recognize safety and liveness properties from a Buchi automaton $m$. This shows that any property rapresented by a Buchi automaton ...
- 349
5
votes
1
answer
180
views
Is there any equation-based method for transforming Büchi-automata to omega-regular language?
I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows.
First we construct a set of equations ...
- 53
3
votes
1
answer
227
views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
- 349
11
votes
2
answers
651
views
Does a given regular language contain an infinite prefix-free subset?
A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other.
The question is:
What is the complexity of checking whether a regular ...
- 113
3
votes
1
answer
105
views
Size bound on Büchi automaton for complement
For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by
$$
\begin{array}{llll}
u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' ...
- 1,977
3
votes
0
answers
96
views
A question on the introduction of the Wagner hierarchy from K. Wagner's original paper
My question is related to the seminal paper On $\omega$-regular sets by K. Wagner, which introduced a hierarchy which is now know as the Wagner- (or Wadge-) hierarchy of $\omega$-regular sets.
In ...
- 1,977
1
vote
1
answer
698
views
Regular safety properties and bad prefixes of $\omega$-regular properties
I have two questions:
By starting with a nondeterministic Büchi automaton (NBA) $\mathcal{A}^{\varphi} = (Q, \Sigma, \rightarrow, I, F )$ for an $\omega$-regular property $\varphi$, we can construct ...
- 163
2
votes
0
answers
215
views
Complexity of DBA-recognizable Omega-Languages
Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
- 153
10
votes
2
answers
511
views
Minimizing Automata accepting $\omega$-words (i.e. infinite words)
What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" ...
- 1,977
1
vote
1
answer
174
views
Example of a $U^\omega$ that is not Deterministic Büchi recognizable
Is there a regular language $U$, for which $U^\omega$ is not a Deterministic Büchi recognizable language. I have been thinking over it for some time, but have been unable to come up with an example.
- 121
1
vote
1
answer
442
views
Adherence of languages and the Dyck language
Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of ...
- 1,977
4
votes
1
answer
129
views
Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata
Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$:
$$
L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in L(\...
- 1,977
5
votes
1
answer
132
views
When does a set of infixes determine a set of ($\omega$-) words
If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for ...
- 1,977
6
votes
0
answers
199
views
Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words
Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton ...
- 363
9
votes
1
answer
515
views
Measurable language which is not $\omega$-regular
Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider
$$
d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)}
$$
to be the metric on $\Sigma^\...
- 407
14
votes
2
answers
884
views
Büchi automata with acceptance strategy
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense :...
- 8,223