All Questions
Tagged with formal-languages computability-theory
11 questions
0
votes
0
answers
197
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 (...
- 309
0
votes
0
answers
105
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 ...
- 3,084
2
votes
2
answers
622
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 ...
- 3,084
4
votes
1
answer
2k
views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) =...
- 105
1
vote
2
answers
480
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
459
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
0
votes
1
answer
158
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,084
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,084
2
votes
1
answer
435
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
1
vote
3
answers
576
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,720
1
vote
4
answers
3k
views
A subset of all languages which is uncountable?
Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all ...
- 2,416