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.
16 questions
27
votes
5
answers
3k
views
Formalizations of the idea that something is a function of something else?
I'll state my questions upfront and attempt to motivate/explain them afterwards.
Q1: Is there a direct way of expressing the relation "$y$ is a function of $x$" inside set theory?
More ...
- 5,343
18
votes
2
answers
4k
views
Can regular expressions be made unambiguous?
When investigating regular languages, regular expressions are obviously a useful characterisation, not least because they are amenable to nice inductions. On the other hand ambiguity can get in the ...
- 516
13
votes
1
answer
2k
views
Are 100% of statements undecidable, in Gödel's numbering? [duplicate]
Gödel's incompleteness theorem shows that there are undecidable statements, i.e., formal logical claims which neither have proofs nor disproofs.
In doing so, Gödel famously enumerated all well-formed ...
- 2,902
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
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
23
votes
1
answer
3k
views
What's the difference between ZFC+Grothendieck, ZFC+inaccessible cardinals and Tarski-Grothendieck set theory?
Say that "U" is the axiom that "For each set x, there exists a Grothendieck universe U such that x $\in$ U", where Grothendieck universes are defined in the usual way (or, if that'...
- 4,897
20
votes
5
answers
1k
views
Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)?
Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:
If $L$ is regular, then $f_L$ is ...
- 118k
10
votes
0
answers
400
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 ...
- 32.4k
6
votes
1
answer
485
views
Show that the positive existential theory is undecidable
To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...
- 309
6
votes
3
answers
1k
views
Proof formalization
I read some time ago some papers about proof formalization. Typically, I began whith this one, from Lamport.
Are there more recent works in this field ?
5
votes
1
answer
464
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 ...
- 3,318
3
votes
1
answer
807
views
Language equivalence between deterministic and non-deterministic counter net
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
- 63
3
votes
2
answers
989
views
Theory interpreted in non-set domain of discourse may be consistent?
Following the blow. I will try to ask question in order to check if I well understand what was pointed. I decide to ask another question, because mathoverflow is not projected to be good environment ...
- 1,626
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
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
-3
votes
1
answer
531
views
Counter net decidability [closed]
Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
- 63