Skip to main content

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
1 vote
0 answers
94 views

Determine equivalences in the generated collection of subgroups and quotients

Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$. Let $\mathcal{C}_1$ be the ...
Zhang Yuhan's user avatar
2 votes
0 answers
86 views

Rewriting systems for finite groups [closed]

This is a question about rewriting systems & languages for finite groups. I'm sure everything must be in the literature somewhere, but I find it hard to navigate the references I have (for example ...
Pierre's user avatar
  • 2,287
6 votes
1 answer
388 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, ...
Марат Рамазанов's user avatar
2 votes
1 answer
124 views

Proof of dynamic programming calculation of Levenshtein distance

Let s1 and s2 are 2 arbitrary strings with lengths l1 and ...
St.Antario's user avatar
7 votes
1 answer
494 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 ...
Joel David Hamkins's user avatar
12 votes
2 answers
926 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),...
Heleyrine Brookvinth's user avatar
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 ...
Lionheart's user avatar
6 votes
0 answers
198 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 ...
Sam Hopkins's user avatar
  • 24.2k
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 ...
Milo Moses's user avatar
  • 2,902
-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 ...
Lionheart's user avatar
17 votes
0 answers
540 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 ...
Pace Nielsen's user avatar
  • 18.7k
-3 votes
1 answer
188 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 (...
Jeroen van Rensen's user avatar
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
4 votes
0 answers
121 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 ...
TomKern's user avatar
  • 429
16 votes
4 answers
1k views

Representing mathematical statements as SAT instances

The following problem (call it THEOREMS) belongs to class NP. Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary. Output: "Yes" if ...
Bogdan's user avatar
  • 781
4 votes
0 answers
170 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 ...
TomKern's user avatar
  • 429
1 vote
0 answers
62 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$...
Paul Blain Levy's user avatar
2 votes
0 answers
64 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 ...
rotas's user avatar
  • 21
3 votes
1 answer
485 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 ...
Tristan Duquesne's user avatar
6 votes
1 answer
561 views

How can I catalog these generalized Collatz problems?

The Collatz conjecture can be expressed in terms of a ruleset in the language $\{x,+,1,\rightarrow,;\}$: $x + x + 1 \rightarrow x+x+x+1+1;$ $x + x \rightarrow x;$ Whenever a number matches the LHS ...
Dan Brumleve's user avatar
  • 2,302
5 votes
1 answer
123 views

Algorithms to factorize words into product of powers

I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references. Let $A$ be a finite set of symbols, are there ...
rtsss's user avatar
  • 477
3 votes
0 answers
406 views

Conversion of proofs between HoTT and ZFC

HoTT provides a foundation of math that remains mysterious for many mathematicians including me. Hence this question. There are several implementations of math based on ZFC, an example being MetaMath. ...
Student's user avatar
  • 5,230
3 votes
3 answers
583 views

Topology induced by context-free language

Is there any way to reasonably define a topology on a context-free-language language? In other words, given a context-free grammar (or perhaps a grammar from an interesting subclass of context-free ...
user1747134's user avatar
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 ...
jg1896's user avatar
  • 3,318
4 votes
0 answers
99 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 ...
Hauke Reddmann's user avatar
12 votes
5 answers
1k views

Predicates of infinite arity

Infinitary logic considers languages being infinite by infinite conjunctions and disjunctions. I wonder why it not considers languages being infinite by relations and functions of infinite arity. ...
Hans-Peter Stricker's user avatar
11 votes
5 answers
1k views

Which Turing machines accept the language of trivial words in a finitely presented group?

Let $G$ be a finitely presented group with generators $g_1, g_1^{-1},\ldots, g_n, g_n^{-1}$. Let $L(G)$ be the language of all those words in $g_1, \ldots, g_n$ which represent the trivial element of $...
Łukasz Grabowski's user avatar
2 votes
1 answer
133 views

What is the cardinality of the set of Dyck natural numbers of semilength $k$?

In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between $\mathbb{N} = \{0,1,2,3,4,\ldots\}$ and $\mathcal{D}_{r_{\...
JustAsking's user avatar
2 votes
0 answers
100 views

Name for the theory of words with equal length, prefix, successors

I've worked with this theory for a while, but I've never been quite sure what to call it: $$(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$$ Where $\Sigma^*$ is the set of finite words on finite ...
TomKern's user avatar
  • 429
8 votes
1 answer
347 views

Is equality of formulas with floor rounding or integer division decidable?

As far as I know, formulae involving rationals and basic arithmetic ($+$, $-$, $\cdot$ and $/$) have decidable equality. Is this still the case if we add floor rounding (or integer division)? Define ...
Manuel Bärenz's user avatar
0 votes
0 answers
113 views

Empty context-sensitive language independent of ZFC?

Is there a simple context-sensitive grammar $G$ such that $L(G)=\emptyset$ is independent of ZFC? $L(G)$ is the formal language generated by $G$.
cslang's user avatar
  • 11
11 votes
6 answers
3k views

Regular languages and the pumping lemma

Let's say that I want to prove that a language is not regular. The only general technique I know for doing this is the so-called "pumping lemma", which says that if $L$ is a regular language, then ...
Andy Putman's user avatar
  • 44.8k
-1 votes
1 answer
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 ...
JustAsking's user avatar
5 votes
2 answers
266 views

Formal languages with non-unique interpretations of terms

In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free ...
Alexey Muranov'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
2 votes
0 answers
64 views

Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language

Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$. Is there a polynomial-time algorithm for uniformly sampling from ...
plegri's user avatar
  • 21
4 votes
0 answers
179 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 ...
user267839's user avatar
  • 5,998
10 votes
2 answers
2k views

What exactly is a judgement?

Before formulating my question, let me briefly sum up what I know about the topic (feel free to correct me if something I claimed is false!). This is for you good to see what my state of knowledge is, ...
user avatar
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'...
Mike Battaglia's user avatar
3 votes
0 answers
722 views

Can third-order arithmetic prove the consistency of second-order arithmetic?

I'm trying to get a deeper understanding of Buss's version of Gödel's speedup proof. In short, if we assume that $Z_0$ is first-order arithmetic, $Z_1$ is second-order arithmetic, and so on, then for $...
John Licato's user avatar
2 votes
1 answer
1k views

When may function (meromorphic) be expanded as power series with coefficients of integers

Let $F$ be meromorphic function, with what properties may it be expanded as power series with coefficients of integers in such a form: $$F=\sum_0^{\infty}a_i x^i,a_i\in \mathbb{N} \bigcup 0,\exists M \...
XL _At_Here_There's user avatar
6 votes
2 answers
1k views

Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or $a^nb^nc^nd^ne^nf^n$

What is the definition of ambiguity of context-sensitive grammar?This is relevant to the definition of inherent ambiguity of context-sensitive language.And any proof for the inherent ambiguity of ...
XL _At_Here_There's user avatar
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 ...
kakaz's user avatar
  • 1,626
4 votes
2 answers
1k views

Semantics of Higher-Order Logics

I've been trying to get to grips with the various semantics commonly discussed in formal logic. Specifically, the nature and role of interpretations of first and higher-order logics is slightly ...
Noldorin's user avatar
  • 820
5 votes
0 answers
357 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 ...
Florian Lehner's user avatar
5 votes
5 answers
3k views

Context free grammar + functions = ?

If you start with the rules for building a context-free grammar and extend them by allowing left-hand nonterminals to be functions of one or more arguments, does that go beyond the definition of a ...
Joey Adams's user avatar
1 vote
2 answers
480 views

Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say: < is a strict partial order and R is an irreflexive and ...
Alberto's user avatar
  • 105
19 votes
3 answers
1k views

Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem: Find a decision procedure for determining if an arbitrary semilinear set is a ...
Tara Brough's user avatar
16 votes
4 answers
7k views

Why do I find Category Theory mostly just a way to make simple things difficult?

I have a basic working knowledge of category thoery since I do research in programming languages and typed lambda-calculus. Indeed, I have refereed many papers in my area based on category theory. ...
RD1's user avatar
  • 213
27 votes
1 answer
1k views

Automatic groups - recent progress

Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental ...
Michal Kotowski's user avatar