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.
158 questions
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 ...
- 5,343
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 ...
- 2,449
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'...
- 4,897
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 ...
- 118k
20
votes
2
answers
734
views
congruence on words: having the same (scattered) subwords of length at most n
For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim_n$ is a congruence of finite ...
- 371
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 ...
- 373
18
votes
2
answers
4k
views
Can regular expressions be made unambiguous?
When investigating regular languages, regular expressions are obviously a useful characterisation, not least because they are amenable to nice inductions. On the other hand ambiguity can get in the ...
- 516
17
votes
1
answer
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 ...
- 1,173
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 ...
- 18.7k
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.
...
- 213
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 ...
- 781
13
votes
2
answers
4k
views
A language complete for NP intersection co-NP
Hi,
Is there any language $L$ know to be complete for $NP \cap co-NP$, i.e. any language $L^{\prime} \in NP\cap co-NP$ reduces in polynomial-time to $L$ and it is known that $L\in NP\cap co-NP$?
...
- 601
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 ...
- 2,902
13
votes
0
answers
323
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,339
13
votes
0
answers
274
views
Eilenberg's rational hiererchy of nonrational automata & languages — where is it now?
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
- 161
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.
...
- 9,720
12
votes
5
answers
3k
views
Generating function of a regular language
It is well known that the generating function of a regular language $L$, i.e. $\sum n_kz^k$ where $n_k$ is the number of words of length $k$ in $L$, is rational, i.e. a quotient of two polynomials $P(...
user6976
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),...
12
votes
3
answers
877
views
Complementation of $\omega$-regular languages in reverse mathematics
Does anyone know where Büchi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over $\...
- 866
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 ...
- 44.8k
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 $...
- 3,897
11
votes
2
answers
2k
views
palindromic subsequences
I'd like any insight or references to the following two conjectures (see the glossary below for definitions):
Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and ...
- 153
10
votes
3
answers
2k
views
How to characterize a Self-avoiding path.
I cannot find any answer to that apparently simple problem :
On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}.
Is there a rule ...
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, ...
user99916
10
votes
3
answers
1k
views
Is there a formal notion of what we do when we 'Let X be ...'?
This is likely an elementary question to logicians or theoretical computer scientists, but I'm less than adequately informed on either topic and don't know where to find the answer. Please excuse the ...
- 1,376
10
votes
1
answer
692
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,312
10
votes
0
answers
400
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 ...
- 32.4k
10
votes
0
answers
2k
views
Is my definition of a context algebra new?
In my DPhil thesis, I defined what I called a context algebra as a model of meaning in natural language. The idea is to mathematically formalise the notion that meaning is determined by context. It ...
- 223
9
votes
1
answer
443
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 ...
- 93
9
votes
0
answers
221
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,893
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 ...
- 5,565
8
votes
3
answers
739
views
What assumptions and methodology do metaproofs of logic theorems use and employ?
In logic modules, theorems like Soundness and completeness of first order logic are proved. Later, Godel's incompleteness theorem is proved. May I ask what are assumed at the metalevel to prove such ...
user2529
8
votes
1
answer
403
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
8
votes
2
answers
943
views
A special class of regular languages: "circular" languages. Is it known?
We can define a subclass of the regular languages. Fix an alphabet $\Sigma$. Define the "circular" languages (actually, the name already exists to denote a different thing it seems, used in the field ...
- 415
7
votes
2
answers
216
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,830
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 ...
- 236k
7
votes
1
answer
548
views
Constructing Metrics for specific Topological Spaces, and Refinements of the Cantor-Space in particular
I have a Problem in general, given some some Topological Space $(X, \tau)$ from which I know it is metrisable, how can I find a metric (that is at best in some sence constructive and easy, at the very ...
- 798
7
votes
2
answers
622
views
Can you hide a letter without losing information?
Consider the following game between Alice and Bob.
$\Sigma$ is a finite nonempty alphabet, $\Delta \notin \Sigma$ denotes
a special symbol, and $k > 0$ is a positive integer constant representing
...
- 73
6
votes
1
answer
485
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: $...
- 309
6
votes
3
answers
1k
views
Proof formalization
I read some time ago some papers about proof formalization. Typically, I began whith this one, from Lamport.
Are there more recent works in this field ?
6
votes
1
answer
955
views
List of open problems of formal languages [closed]
As we know, there are some open problems of formal languages. I am wondering if there is a somehow complete list of open problem of formal languages. If there isn't such a list, can we make it one as ...
- 3,084
6
votes
1
answer
516
views
Growth zeta-functions of regular languages
Dear All,
my following question may be known and ought to be known, so in case it is folklore please could you give me the references.
To start, it is obvious that growth of rational languages are ...
- 1,437
6
votes
1
answer
774
views
word problem in free Burnside groups (and other torsion groups)
Question 1. Is it known that for some free Burnside groups the word problem is undecidable?
Provided that the answer is negative, what about the following easier question.
Question 2. Is there a ...
- 3,897
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, ...
- 125
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 ...
- 2,302
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 ...
- 3,084
6
votes
1
answer
135
views
Generalising the adherence operator and its closure properties with regard to regular (rational) languages
Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-...
- 798
6
votes
1
answer
949
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 ...
- 25.4k
6
votes
1
answer
165
views
Separating infinite words sharing factors by automata
Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.
Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...
- 798
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 ...
- 24.2k