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.
156
questions
2
votes
1
answer
90
views
Proof of dynamic programming calculation of Levenshtein distance
Let s1 and s2 are 2 arbitrary strings with lengths l1 and ...
- 203
6
votes
1
answer
265
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, ...
- 109
6
votes
0
answers
196
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 ...
- 23.2k
-3
votes
1
answer
176
views
Propositional logic without rules of inference and assumptions (except MP) [closed]
I was wondering whether it would be possible to do propositional logic without any rules of inference and assumptions (except modus ponens).
I have the following axioms:
$ p \to (q \to p) $
$ (p \to (...
12
votes
2
answers
854
views
An overview of mathematical-logical approaches in formalizing natural languages
Crossposted on Mathematics SE
I am an undergraduate mathematics student with a keen interest in pursuing research in the formalization of natural languages (from a more mathematical-logical approach),...
6
votes
1
answer
483
views
Normal form for terms in language with two ring structures
Suppose I have two different ring structures on the same domain $\langle R,+,\cdot,0,1\rangle$, $\langle R,\oplus,\otimes,\bar 0,\bar 1\rangle$ and I throw the structures together into a single common ...
- 230k
17
votes
0
answers
532
views
Are there more true statements than false ones?
It is a nontrivial fact that half the primes are $\equiv 1 \pmod{4}$ and the other half are $\equiv 3\pmod{4}$. The Chebyshev bias suggests, however, that the latter class of primes is winning the ...
- 18.3k
3
votes
1
answer
787
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
1
answer
521
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
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 ...
- 2,837
4
votes
0
answers
116
views
Are semilinear sets piecewise periodic?
I wanted to check my understanding of semilinear sets before I give a talk on them, and I haven't been able to find this exact perspective in any of the sources I've read through. Is it correct, and ...
- 429
1
vote
0
answers
58
views
The set of closed untyped $\lambda$-terms is not context-free?
The set of untyped $\lambda$-terms is obviously context-free. But, according to Barendregt's paper Discriminating coded lambda terms (six lines before Theorem 1.5), the set of closed untyped $\lambda$...
- 1,382
2
votes
0
answers
61
views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
4
votes
0
answers
162
views
Corollaries of Kleene's Theorem (Regular Languages)
Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the ...
- 429
4
votes
0
answers
97
views
String rewrite system for algebraic knots/links?
$\newcommand\over{\vert}\newcommand\rot[1]{\mathopen<#1\mathclose>}$By its definition, an algebraic tangle, and by extension, its closure (knot or link) can be written as a string (of ...
- 4,739