# Questions tagged [formal-languages]

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

155 questions
Filter by
Sorted by
Tagged with
80 views

### What is the max number of self-segregating words of length n?

A set of words S is called self-segregating if you don't need whitespaces to read them. It means that for any two words from S no new words from S arise between them. For example the set ab, bc, ac, ...
193 views

### Filling in some missing squares for classes of power series

This question concerns various important classes of formal power series. For concreteness and convenience, let us work with power series $F(x) = \sum_{n\geq 0}c_n x^n \in \mathbb{C}[[x]]$, i.e., with ...
• 22.9k
159 views

• 129
125 views

### Prove using Dyck naturals: for $n \in \mathbb{N}_{+}$ and big enough $k \in \mathbb{N}_{+}$, $p_{k-1} < \cdots < np_{k-a_{n}}$ (a is A073093)

While conducting research in connection with arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I noticed certain interesting patterns, one of which inspired the ...
• 129
442 views

### Is there an equivalent of the incompleteness theorems/halting problem in category theory?

Taking the doctrine of computational trinitarianism ( https://ncatlab.org/nlab/show/computational+trinitarianism ), if one understands the incompleteness theorems as the "logic" version, and ...
173 views

### A lemma from Jarden's and Lubotzky's paper 'Elementary equivalence of profinite groups'

I have a question about a reduction argument from Jarden's and Lubotzky's paper 'Elementary equivalence of profinite groups' in Lemma 1.1 on page 3: Lemma 1.1: For each positive integer $n$ and each ...
• 6,000
432 views

### Computational complexity of proof verification

Let $\mathcal{L}$ be a recursive first-order theory, with a deductive system $\Xi$ (for instance, Hilbert-Ackerman proof system). Let $\phi$ be a formula and let $l=(\psi_1, \ldots, \psi_n=\phi)$ be a ...
• 2,683
353 views

### Self avoiding walks and context free languages

Let $G$ be an infinite, locally finite, connected graph whose arcs (oriented edges) are labelled by letters in a finite alphabet $\Sigma$ such that arcs starting in the same vertex are labelled by ...
• 2,531
1 vote
49 views

### Name for a class of languages closed under union, inverse generalised sequential machine mappings and intersection with regular languages

I asked this question on the TCS stackexchange but have so far received no answer: Is there a name for classes of languages closed under finite union, inverse generalised sequential machine mappings ...
• 383