1
vote
1answer
101 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 ...
4
votes
1answer
488 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) ...
1
vote
2answers
261 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 ...
4
votes
3answers
286 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 ...
0
votes
1answer
148 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 ...
0
votes
1answer
606 views

When may Function (meromorphic) be expanded as power series with coefficients of integers

Let F be meromorphic function,with what properties may it expanded as power series with coefficients of integers in such a form: $$F=\sum_0^{\infty}a_i x^i,a_i\in \mathcal{N} \bigcup 0,\exists M ...
2
votes
1answer
263 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 ...
2
votes
3answers
398 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 ...
1
vote
4answers
2k 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 ...