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.

Filter by
Sorted by
Tagged with
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 ...
Michael Bächtold's user avatar
17 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 ...
Max's user avatar
  • 506
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(...
user avatar
5 votes
1 answer
304 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 ...
J.-E. Pin's user avatar
  • 851
22 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'...
Mike Battaglia's user avatar
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 ...
Qiaochu Yuan's user avatar
12 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 ...
Milo Moses's user avatar
  • 2,809
10 votes
0 answers
397 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 ...
Gro-Tsen's user avatar
  • 29.9k
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 ?
6 votes
1 answer
475 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: $...
Mary Star's user avatar
  • 299
5 votes
1 answer
428 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 ...
jg1896's user avatar
  • 2,683
3 votes
3 answers
545 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 $$\...
Xorwell's user avatar
  • 434
3 votes
2 answers
961 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 ...
kakaz's user avatar
  • 1,596
3 votes
1 answer
774 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 ...
Lionheart's user avatar
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 ...
StefanH's user avatar
  • 798
-3 votes
1 answer
518 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 ...
Lionheart's user avatar