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.
155
questions
1
vote
2
answers
474
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 ...
- 105
4
votes
3
answers
448
views
Existential quantification over regular predicates
A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of ...
- 105
2
votes
1
answer
233
views
5
votes
0
answers
320
views
Büchi automata with acceptance strategy [closed]
I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can ...
- 1,291
1
vote
2
answers
2k
views
Translate a buchi automaton to LTL
How can I translate a Büchi automaton A to LTL(linear temporal logic) if $L(A)$ is definable in the LTL?
MY idea is : Büchi automaton $A$ ===> QPTL ===> LTL
I know that given any Buchi ...
- 73
2
votes
1
answer
519
views
Notation for ends of a string
I work now a lot with strings of characters and other finite sequences and found that I need many times a good notation for "cutting the end" a string. If $a$ is a finite sequence and $a'$ is its ...
user22882
3
votes
0
answers
864
views
Question about $\omega$-regular languages
As most of you already know, in model checking most linear-time properties are either safety properties or liveness properties. A linear time property is usually described with an $\omega$-regular ...
- 173
3
votes
2
answers
772
views
Certain type of regular languages
Dear All,
there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that ...
- 1,427
12
votes
0
answers
268
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 ...
- 151
4
votes
2
answers
2k
views
Are context-free languages with context-free complements necessarily deterministic context-free?
Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.
If $L$ and $L'$ are both context-free, are ...
- 387
0
votes
1
answer
157
views
any given c.e.set has number M whose power bounds the corresponding elements of S?
For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq ...
- 3,000
3
votes
1
answer
519
views
Study of free monoids of the recursive S. Eilenberg.
Compared to the usual treatises on recursion (eg, Rogers H. "Computability and Undecidability." McGraw-Hill, New York) the book of Samuel Eilenberg & Calvin C. Elgot "Recursiveness" treats such ...
- 4,125
7
votes
2
answers
617
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
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 \...
- 3,000
2
votes
1
answer
254
views
The intersection of Block Groups and R-trivial (finite) monoids
Let $\textbf{BG}$ be the pseudovariety of block groups, also known as $\textbf{EJ}, \textbf{PG},\ldots,\text{etc.}$(see [1]), and let $\textbf{R}$ be the pseudovariety of R-trivial monoids, by the ...
- 434
3
votes
3
answers
545
views
Finite variation and idempotent languages and automata
Let $L$ be a regular language over alphabet $\Sigma$ and let $A:=(Q,\Sigma,\delta, q_0, F)$ be the minimal DFA recognizing $L$. For every $w\in \Sigma^*$ define the variation of $w$ w.r.t. $L$ by
$$\...
- 434
1
vote
1
answer
157
views
On the boundedness of linear representations of formal power series of languages.
Let $\Sigma$ be a finite non-empty set of symbols (i.e. an alphabet). Fix $\pi, \eta\in\mathbb{R}^{1\times m}$ and for every $\sigma\in\Sigma $ fix $A(\sigma)\in\mathbb{R}^{m\times m}$.
We also ...
- 434
3
votes
1
answer
408
views
density of formal language？
let $\sum_0^n l_i x^i$ and $\sum_0^n 2^i x^i$ be generating function of L a given language and the closure over alphabet $\Sigma= \{0,1 \}$ when $n\to\infty$.
let$$D=\frac{\sum_0^n l_i }{\sum_0^n 2^...
- 3,000
0
votes
1
answer
279
views
What is the conditional probability or probablity of classes of languages?
What is the conditional probability or probability of classes of languages?
Let $E,C,S,F,R $ be the class of computably enumerable languages,computable languagesl,context-sensitive anguages,context-...
- 3,000
2
votes
4
answers
1k
views
Are inference laws consistent?
Please forgive me if this question sounds too naive... Well, in mathematics a formal theory consists of a collection of axioms $T$ (such as Peano arithmetics, or Group Theory, or ZFC), which ...
- 22.7k
6
votes
1
answer
506
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,427
2
votes
1
answer
415
views
Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)
Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
- 143
6
votes
1
answer
740
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,887
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,887
1
vote
4
answers
16k
views
REGULAR TM is undecidable [closed]
I'm sure you all are familiar with Theorem 5.3 from Sipser's TOC book:
S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x:
(a) If x = ...
- 21
2
votes
1
answer
223
views
Parsing of Stochastic Contex-Free Grammars (SCFGs)
I am interested in parsing of general SCFGs.
I am aware of the Earley parser for the general CFGs. The only general algorithm for parsing SCFGs that I am aware of is the Earley-Stolcke parser : http:/...
- 21
20
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 ...
- 383
13
votes
3
answers
857
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 $\...
- 876
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,628
1
vote
1
answer
301
views
Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?
Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}?
One case this is possible is when ...
- 454
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
8
votes
2
answers
923
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
3
votes
3
answers
915
views
'Closure' of CFLs under complementation and intersection
Consider two context-free languages $L_1, L_2$. Of course, $L_1 - L_2, L_1\cap L_2, \bar{L}_1$, etc. are not necessarily context-free, but they are context-sensitive (the second is easy, the other two ...
- 793
1
vote
3
answers
558
views
Graph properties: definability and decidability
[This is a side question to Supervenience in mathematics.]
There are graph properties that are not FO-definable, but MSO-, TC-, or LFP-definable. There may be other graph properties that are not MSO-,...
- 9,628
17
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 ...
- 506
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 ...
1
vote
3
answers
1k
views
A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm
Let $L$ be a language in $NP$. Then are there any results on whether there exists a polynomial-time algorithm (polynomial in the length of the description of $L$) to decide whether $L \in P$? Are ...
- 591
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$?
...
- 591
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 ...
- 800
3
votes
2
answers
568
views
What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?
For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. :
$$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \...
- 776
4
votes
0
answers
305
views
To what extent MSO = WS1S, when adding relations?
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...
- 776
4
votes
1
answer
385
views
Vocabulary on monoid periodicity
I'm learning about periodic languages, and I'm confused over the vocabulary used to describe the periodicity of (syntactic) monoids.
If I understand correctly, a monoid M is periodic if :
$$(\forall ...
- 776
3
votes
1
answer
3k
views
Can I have an LL grammar for every deterministic context free language?
Every deterministic context free grammar can be represented by a LR(1) grammar, so this question can be rephrased as: can I build an equivalent LL(k) grammar from every LR(k) grammar? Can I have an ...
- 133
0
votes
1
answer
183
views
Building optimal rewriting rules.
Please give me some pointers where I can learn more about the following problem:
I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. ...
- 173
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
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 ...
- 151
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 ?
3
votes
2
answers
964
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 ...
- 1,596
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
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,429