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.
143
questions
4
votes
0
answers
78
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,019
3
votes
0
answers
185
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. ...
- 4,005
2
votes
0
answers
49
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 ...
- 21
2
votes
0
answers
81
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 ...
- 239
0
votes
0
answers
91
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$.
- 11
4
votes
0
answers
68
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 ...
- 467
2
votes
1
answer
98
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_{\...
- 129
-1
votes
1
answer
117
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 ...
- 129
3
votes
1
answer
282
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 ...
- 141
4
votes
0
answers
166
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 ...
- 723
5
votes
1
answer
248
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 ...
- 1,713
5
votes
0
answers
102
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 ...
- 2,206
1
vote
0
answers
31
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 ...
- 373
3
votes
0
answers
446
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 $...
- 31
8
votes
1
answer
308
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 ...
- 5,327
0
votes
1
answer
170
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
...
- 31
1
vote
0
answers
191
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 ...
- 675
22
votes
5
answers
2k
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,043
1
vote
1
answer
145
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 ...
- 403
2
votes
1
answer
59
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 ...
- 693
15
votes
3
answers
704
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 ...
- 701
4
votes
0
answers
243
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 ...
- 2,144
0
votes
0
answers
67
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 ...
- 2,592
1
vote
0
answers
198
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 ...
- 2,592
2
votes
1
answer
159
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 ...
- 21
8
votes
1
answer
371
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"...
- 81
3
votes
2
answers
362
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 ...
- 273
8
votes
2
answers
1k
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, ...
user99916
5
votes
1
answer
380
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 ...
- 3,503
5
votes
2
answers
430
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,...
- 61
10
votes
0
answers
377
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 ...
- 21.7k
13
votes
0
answers
289
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 (...
- 2,251
9
votes
1
answer
560
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 ...
- 2,242
3
votes
1
answer
664
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 ...
- 33
-2
votes
1
answer
264
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 ...
- 7
0
votes
0
answers
189
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 (...
- 299
6
votes
1
answer
449
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: $...
- 299
0
votes
0
answers
216
views
Probability of substring given string production probabilities
I originally posted this question on the Math StackExchange, but have not received answers there and thought it might be more appropriate to post it here.
Let $\Sigma$ be an alphabet and let $y = x_1 ...
- 1,577
2
votes
0
answers
41
views
Relation between indexed languages (OI-macro or context-free tree) and scattered context languages
I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...
- 21
1
vote
1
answer
133
views
Terminology for set of infinite strings with a certain prefix
Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology.
Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...
- 8,215
1
vote
1
answer
224
views
The automorphism groups of smallest grammars of a language string are isomorphic
Let $s \in \Sigma^*$ be a formal language string. Consider the automorphism group of $s$, defined to be the set of all permutations of positions of $s$ that leave $s$ fixed. For instance $G(abab) = \...
9
votes
0
answers
182
views
Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?
Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"?
Or is there something else that states ...
- 1,833
7
votes
2
answers
193
views
Is this variant of the balanced bracket language context free?
Consider the language generated by the following context free grammar:
$$
S \to SS \quad S \to () \quad S \to (S) \quad S \to [] \quad S \to [S]
$$
There is a one-to-one correspondence between this ...
- 3,546
0
votes
0
answers
98
views
Counting path generating sentences in a specific formal language
Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language?
For example, we know that if the grammar is context-free ...
- 2,592
6
votes
2
answers
201
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 ...
- 1,370
3
votes
3
answers
188
views
Are there any results on well-quasi-ordering of languages?
There are a number of papers that I can find about well-quasi-orders in formal lnaguage theory, by Kunc, de Luca, D'Alessandro, and Varricchio, among others. I am interested, however, in well-quasi ...
- 131
6
votes
2
answers
878
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 ...
- 2,592
8
votes
1
answer
418
views
Is there a name for infinite words containing every finite words?
Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html
But requiring that every finite words occurs is weaker than this property. So I'm ...
- 83
1
vote
0
answers
55
views
Question about link between non-terminals of grammars and variables of Diophantine equations
If we change the right arrow in the rewriting rules of grammar into equators , changes all terminals into x and keep the non-terminals unchanged,we get system of equations.In some cases,those ...
- 2,592
1
vote
0
answers
62
views
Is it possible to classify all the inequivalent classes of first order sentence with quantifier rank fixed
It is known that for symbols with finite many relations, the number of inequivalent class of first order sentence with quantifier rank $m$ is finite. But is it possible to list (classify) them? At ...
- 11