The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
45 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
88 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.
6
votes
1answer
25 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 ...
2
votes
1answer
227 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 – ...
1
vote
1answer
84 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 ...
6
votes
1answer
115 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 ...
5
votes
1answer
69 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 ...
2
votes
1answer
107 views

Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)

Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$ the set of factors (consecutive finite subsequences) of length $n$ and consider the set $$ K_n(\xi) = ...
5
votes
1answer
108 views

What prefix and factors determine a ultimately periodic word uniquely

Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all ...
0
votes
1answer
642 views

Is there any danger far from home? (Edited & Revised Version) [closed]

The notion of formal proof is defined by finite sequences ($<\omega$ - sequences) of sentences. In some sense if a sentence $\sigma$ is (finitely) provable from the theory $T$ it is very "near" to ...
0
votes
0answers
64 views

Proof of conjecture that permutation-free automata restrict the possible states visitable from a stringset sharing prefixes and infixes

An automaton $\mathcal A = (X, Q, \delta, q_0)$ is called permutation-free iff no word $w \in X^*$ induces a nontrivial permutation of a subset of the states of $\mathcal A$. More formally for any $R ...
2
votes
0answers
127 views

Comparing two metrics on the space of infinite sequences and relating open and closed sets

Let $X = \{ 0, 1 \}$ and $X^{\mathbb N_0} = \{ x_0 x_1 x_2 \ldots : x_i \in X \}$ be the space of all infinite sequences, then a metric could be defined on it $$ d(u,v) := \frac{1}{2^r} \mbox{ with } ...
3
votes
0answers
73 views

The Kleene theorem

By the Myhill–Nerode theorem a language $L$ is accepted by a finite automaton iff it consists of classes of a finite congruence. By the Kleene theorem $L$ is accepted by a finite automaton iff it ...
4
votes
2answers
263 views

Concatenation of strings [closed]

We have two strings (i. e., finite tuples) $A$ and $B$. We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
3
votes
1answer
96 views

Subsets of $\omega$-regular lanuages accepted by automata with special acceptance condition

Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words: The automata accepts $\xi \in X^{\omega}$ with respect to $F$ ...
3
votes
2answers
164 views

Ordering on words

What are the known computation-friendly well-orderings on words from $A^*$, where $A$ is a finite alphabet, except the standard weightlex and syllable-order?
2
votes
1answer
96 views

Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular

Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages $$ L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi ...
4
votes
1answer
125 views

Progress on group languages characterizations

Def. A group language is a recognizable language whose syntactic monoid is a group. q1. Is it known a "nice" combinatorial characterization of group languages ? q1.1. If no, is it well understood ...
2
votes
1answer
64 views

Varieties of rational languages and (pseudo-)varieties of finite monoids, question regarding closure property

Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff ...
5
votes
1answer
159 views

Is it decidable whether the support of a rational $\mathbb{Z}$-series is a regular language?

Let $S \in \mathbb{Z}\langle\langle A\rangle\rangle$ be a rational series in noncommutative variables. The support of $S$ is the set of all words $u \in A^*$ such that $(S, u) \not= 0$. It is ...
2
votes
2answers
156 views

Generating function of factorable binary words

A word $w$ on the alphabet $A := \{0, 1\}$ is factorable if \begin{equation} w = u^k \mbox{ where } u \in A^* \mbox{ and } k \geq 2. \end{equation} Let $L$ be the language of the set of ...
7
votes
1answer
244 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 ...
1
vote
1answer
73 views

Simple asymptotic combinatorics - how many words are there in a certain weight category? [closed]

Given the set of all binary strings of length n, I am looking at the "middle" of these strings, weight-wise. Namely, I am trying to calculate how many words are there whose weight is between n/2 - ...
1
vote
3answers
258 views

Is there an recursively axiomatized system with infinitely many proofs for some propositions or a proposition [closed]

Is there any recursively axiomized system with infinitely many proofs for some propositions or a proposition? So we will have at least one proposition which is deduced from the recursively axiomatic ...
0
votes
0answers
163 views

Extended definition of unambiguous language and the existence of unambiguous grammar

Let's extend the unambiguity of language and grammar as follows: a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or ...
5
votes
1answer
390 views

List of open problems of formal languages

As we know ,there are some open problems of formal languages,I am wandering if there is a somehow complete list of open problem of formal languages,or if there is no somehow complet one,May we make it ...
20
votes
2answers
546 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 ...
3
votes
3answers
498 views

L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below). I'm interested to know how could one arrange the rules of ...
0
votes
2answers
342 views

Any grammar for the language $L =a^p$, $p$ is prime number of $\mathbb{N}$

Any grammar for the language $$L =a^p,\text{ $p$ is prime and }p\in \mathbb{N}?$$ Is such a grammar related to any question of number theory like RH or the conjecture of twin primes?
5
votes
1answer
332 views

How to work out a grammar if we know the language?

How to work out a grammar if we know the language? Or at least How to work out a grammar if we know the language that is restricted to a special kind like CFL or CSL? For example,we know ...
2
votes
0answers
48 views

Is any CFL intersection,union of CFLs that are not inherently ambiguous?

Is any CFL intersection,union of CFLs that are not inherently ambiguous?
4
votes
0answers
87 views

Properties of classical automata preserved in Büchi automata

Given two NFW $A$ and $B$, we regarded $A$ and $B$ as Büchi automata. We can show that the containment property is not preserved in Büchi automata. That is, we can construct a example: $L(A) ...
7
votes
5answers
445 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 ...
0
votes
1answer
256 views

prove (a+b)*=a*(ba*)* [closed]

formal language and automata theory regular expessions (a+b)* =a*(ba*)* please answer I want the proof thank you
0
votes
1answer
110 views

Can decidability results for monadic second-order logic be extended to monadic higher-order logics?

Call a higher-order logic fully monadic if and only if all of its predicate constants (at any order) and higher-order variables (at any order) are monadic (and it has no function symbols). In ...
4
votes
1answer
421 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) ...
11
votes
2answers
788 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's unclear, in this ...
2
votes
2answers
598 views

All properties of a mathematical object

This is primarily a question about related literature. I am looking for specific references, or terminology that I can use to search for references. Let A a well defined mathematical structure of ...
1
vote
2answers
253 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
271 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 ...
1
vote
1answer
144 views

Is complement of LL(k) grammar context free?

Is complement of LL(k) grammar context free?
5
votes
0answers
177 views

Büchi automata with acceptance strategy

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 always remove ...
1
vote
2answers
362 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 ...
1
vote
1answer
352 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 ...
2
votes
0answers
310 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 ...
3
votes
2answers
730 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 ...
11
votes
0answers
185 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 ...
3
votes
2answers
764 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 ...
0
votes
1answer
147 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 ...
2
votes
1answer
434 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 ...