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
2
votes
1answer
85 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_{\...
-1
votes
1answer
108 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 ...
3
votes
1answer
194 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 ...
4
votes
0answers
165 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 ...
5
votes
1answer
205 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 ...
5
votes
0answers
94 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 ...
1
vote
0answers
30 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 ...
3
votes
0answers
366 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 $...
8
votes
1answer
266 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 ...
0
votes
1answer
159 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 ...
1
vote
0answers
185 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 ...
18
votes
5answers
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 ...
1
vote
1answer
144 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 ...
2
votes
1answer
54 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 ...
15
votes
3answers
641 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 ...
4
votes
0answers
221 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 ...
0
votes
0answers
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 ...
1
vote
0answers
163 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
votes
1answer
137 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 ...
7
votes
1answer
341 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"...
3
votes
2answers
296 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 ...
6
votes
2answers
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, ...
5
votes
1answer
365 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 ...
5
votes
2answers
395 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,...
10
votes
0answers
362 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 ...
13
votes
0answers
274 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 (...
9
votes
1answer
509 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 ...
3
votes
1answer
555 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 ...
-2
votes
1answer
261 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 ...
0
votes
0answers
182 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 (...
6
votes
1answer
432 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: $...
0
votes
0answers
206 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 ...
2
votes
0answers
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 ...
1
vote
1answer
121 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 ...
1
vote
1answer
218 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
0answers
159 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 ...
7
votes
2answers
187 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 ...
0
votes
0answers
96 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 ...
6
votes
2answers
195 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 ...
3
votes
3answers
180 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 ...
5
votes
2answers
767 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 ...
8
votes
1answer
394 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 ...
1
vote
0answers
54 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 ...
1
vote
0answers
61 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 ...
0
votes
0answers
67 views

Two sets of strings resulted from a set represented by binary and decimal code are in the same class of languages?

Two sets of strings resulted from a set represented by binary and decimal code are in the same class of languages as regular languages,context-free languages,context-sentive languages ,computable ...
6
votes
1answer
638 views

Complexity of counting words of given length in regular or context-free language

Let $L$ be a regular or context-free language over alphabet $\{0,1\}$. What is the complexity of counting words of length $n$ in $L$? Is it possible to efficiently find if for given $n$ all words ...
1
vote
0answers
243 views

Examples of languages that are in P and are not in CFL [closed]

Any examples of languages that are in P(polynomial time to recognize it) and are not in CFL(context-free language)?The more the better.
17
votes
1answer
2k views

Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...
5
votes
1answer
462 views

Expressive power of first-order category theory

Given the signature $\lbrace \mathsf{dom}, \mathsf{cod}, \mathsf{id},\circ \rbrace$ and the axioms of category theory – which are expressible in the signature's first-order (FO) language – ...
2
votes
2answers
475 views

Every infinite c.e.language is infinite or finite union of regular languages including at least one infinite regular language?

Is Every infinite c.e.language infinite or finite union of regular languages including at least one infinite regular language? And is every infinite c.e.language that is not indexed language(that may ...