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
0 votes
0 answers
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, ...
Марат Рамазанов's user avatar
6 votes
0 answers
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 ...
Sam Hopkins's user avatar
  • 22.9k
-3 votes
1 answer
159 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
12 votes
2 answers
807 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
6 votes
1 answer
477 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
17 votes
0 answers
526 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.1k
3 votes
1 answer
776 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
-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
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,817
4 votes
0 answers
107 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
1 vote
0 answers
53 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
58 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
4 votes
0 answers
156 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
4 votes
0 answers
94 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
3 votes
0 answers
362 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,028
2 votes
0 answers
59 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
2 votes
0 answers
98 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
0 votes
0 answers
110 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
5 votes
1 answer
119 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
2 votes
1 answer
130 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
-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
3 votes
1 answer
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 ...
Tristan Duquesne's user avatar
4 votes
0 answers
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 ...
user267839's user avatar
  • 6,000
5 votes
1 answer
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 ...
jg1896's user avatar
  • 2,683
5 votes
0 answers
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 ...
Florian Lehner's user avatar
1 vote
0 answers
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 ...
Tara Brough's user avatar
3 votes
0 answers
647 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
8 votes
1 answer
339 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
1 answer
193 views

Does the fixed point lemma / diagonalization require capturing or not?

Peter Smith's formulation of the diagonalization lemma is essentially as follows, from Theorem 47 of his (fantastic) online book: If theory T extends Robinson Arithmetic, and P is an one-place open ...
John Licato's user avatar
1 vote
0 answers
202 views

Is it possible to construct a formal language that allows to refer to specific real numbers that encode ordinals accidentally writable by an ITTM?

Let $A$ denote a particular (fixed) algorithm to encode ordinals as real numbers. The exact technical description of $A$ is irrelevant for this question: it can be any algorithm that is mathematically ...
lyrically wicked'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
1 vote
1 answer
155 views

Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?

Recently, a student and I have been working through Waksman's paper ``An Optimum Solution to the Firing Squad Synchronization Problem.'' The paper claims that for any value of $n$, the proposed ...
Andrew Penland's user avatar
2 votes
1 answer
69 views

For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset

Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state ...
StefanH's user avatar
  • 798
16 votes
4 answers
955 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
6 votes
1 answer
470 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,254
0 votes
0 answers
74 views

Transformation or correspondence between language and real number

As we know, formal language can be regarded as a set of strings of alphabet, and real number can be regarded as sequence generated by set of integers, for example, denominators of the simple continued ...
XL _At_Here_There's user avatar
1 vote
0 answers
253 views

What does homomorphism between languages mean to the correspoding Turing Machines?

According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the ...
XL _At_Here_There's user avatar
2 votes
1 answer
200 views

Alternative notation for Kleene star

I am writing a paper which use two different operations on sets of works $X$, both of which I want to denote by a star, $X^{\ast}$. One of these operations is the Kleene star, and for whatever reason ...
user111368's user avatar
8 votes
1 answer
393 views

Can ETCC/ETCS talk about 'size issues'?

In material set theories (like ZFC), one can prove that there is no set of all sets. Can one prove a similar statement in ETCS? This exact statement "there is no set x such that y in x for every set y"...
user106042's user avatar
3 votes
2 answers
498 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
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
5 votes
1 answer
393 views

What do we call this quantifier ("binder")?

There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...
goblin GONE's user avatar
  • 3,693
5 votes
2 answers
532 views

Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...
Distance's user avatar
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
  • 30.1k
13 votes
0 answers
314 views

Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters (...
Vince Vatter's user avatar
  • 2,329
9 votes
1 answer
654 views

Coherence and rewriting

In category theory there are numerous coherence theorems (https://ncatlab.org/nlab/show/coherence+theorem). One example is the Mac Lane's coherence theorem for monoidal categories. This and probably ...
Dimitri Chikhladze's user avatar
3 votes
1 answer
977 views

How to get $\omega$-regular expression from buchi automaton

Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions? It is extremely ...
Fabio's user avatar
  • 33
-2 votes
1 answer
272 views

Deterministic Finite Automata question [closed]

I am very new to finite automata, and I came across an issue in my professors lecture slides which I think is wrong, and I'd wonder if any of you could confirm: Alphabet: {1} Automata Surely the ...
Danny's user avatar
  • 7
0 votes
0 answers
195 views

Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ? How can we prove the (...
Mary Star's user avatar
  • 299
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