# Tagged Questions

The study of formal languages (sets of strings or trees over an alphabet), rewriting systems and algorithms, recognition automata/algorithms, and related questions.

300 views

### What do we call this quantifier (“binder”)?

There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...
130 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,...
278 views

### Computing the ordinal of a rational language well-partially-ordered by the subword relation

Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...
174 views

### Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters. The ...
322 views

### Coherence and rewriting

In category theory there are numerous coherence theorems (https://ncatlab.org/nlab/show/coherence+theorem). One example is the Mac Lane's coherence theorem for monoidal categories. This and probably ...
103 views

### How to get $\omega$-regular expression from buchi automaton

Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions? It is extremely ...
91 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 ...
150 views

### Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ? How can we prove the (...
298 views

33 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 ...
Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology. Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...