Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

Filter by
Sorted by
Tagged with
1 vote
0 answers
82 views

Can we describe any context-sensitive language by a grammar without left recursion?

The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
user avatar
2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
user avatar
  • 91
5 votes
1 answer
161 views

Establishing competing memory limits for pushdown automata

Let $L$ be the language of all even-length strings whose first half is a palindrome. Let $L$ be the language of all even length strings whose first half is imbalanced—with an unequal number of $\...
user avatar
0 votes
1 answer
22 views

where to read about PSO (partial store order) memory model

I have been reading about TSO (total store order) memory models for concurrent programs, but I can not find resources for PSO (partial store order) memory models. Can someone please point to resources....
user avatar
9 votes
1 answer
197 views

Words of the form $(a^n b)^n$ in a context-free language

Question For a language $L \subset \{a,b\}^*$, denote $N(L) = \{ n \geq 0 \mid (a^n b)^n \in L \}$. If $L$ is context-free, is $N(L)$ necessarily semilinear, meaning that $n \in N(L) \iff n+p \in N(L)$...
user avatar
5 votes
2 answers
204 views

Are trace monoids always syntactic monoids?

There's an assertion on Wikipedia that a trace monoid is a syntactic monoid because $x w y \equiv x v y$ implies that $w \equiv v$. I don't see how that follows as a consequence, and I can't find any ...
user avatar
1 vote
1 answer
88 views

Bounded non-emptiness intersection of deterministic context-free grammars

Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
user avatar
8 votes
1 answer
159 views

Word equations with integer parameters

This is mainly a reference request. Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows: $$e,e':= w\mid w^i \mid e\cdot e'$$ Where $w\in\Sigma^+$ is a word, and $i$ is an ...
user avatar
  • 7,653
5 votes
0 answers
202 views

Satisfiability and a Galois Theory Analog

Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows: $$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$ where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
user avatar
5 votes
1 answer
210 views

Name for words without squared symbols

Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
user avatar
  • 161
6 votes
1 answer
157 views

star height of star-free languages

I'm interested in the (restricted) star-height of star free-languages. Recalling the definitions: the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is $0$ if $\mathtt{e}= \...
user avatar
  • 193
7 votes
2 answers
148 views

Algebraic characterisation of star-free safety languages

It is known that star-free languages are definable by aperiodic syntactic monoids. But is there any algebraic characterisation of star-free safety $\omega$-languages? Edit: A language $L$ is safety if ...
user avatar
  • 1,122
3 votes
1 answer
579 views

Determinising unambiguous automata without exponential blowup

Is it possible to determinise unambiguous finite automata without exponential blowup in the number of states? I think it should not be possible but I am unable to come up with counterexamples.
user avatar
1 vote
0 answers
75 views

Parametrization of context-sensitive language in polynomial time

Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length. Can we always find $f:\Sigma^*\to L$ computable in polynomial time in ...
user avatar
  • 11
6 votes
1 answer
189 views

Context Free Grammar For Complement Of { www | ... } with minimal pumping length?

Let $L := \{ w^3 | w \in \{0,1\}\}^C$ be the complement of the language of words that are not the 3rd power of a word over $\Sigma = \{0,1\}$. Let's define the largest minimal pumping length of a ...
user avatar
  • 389
7 votes
1 answer
169 views

Example of an context-sensitive language with a specific number of words of length $n$

Let $s_L(n)$ denote the number of words of length $n$ in $L$. For context-free languages it is known that $s_L(n)$ is either polynomial or exponential. For context-sensitive languages this is probably ...
user avatar
5 votes
2 answers
191 views

Reference request: An algebraic characterisation of LTL[XF]-definable word languages

I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1). A similar ...
user avatar
1 vote
0 answers
82 views

Take a natural quotient of context-free grammars

Fix a finite alphabet. Let $\mathrm{CFG}$ be the set of context-free grammars on this alphabet, $\mathrm{CFL}$ the set of context-free languages, $\mathrm{UG}$ the set of unrestricted grammars and $\...
user avatar
  • 41
3 votes
0 answers
81 views

Useful notion of ambiguous growing context-sensitive language

As far as I understand there is no useful notion of ambiguous context-sensitive language. For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
user avatar
  • 41
0 votes
1 answer
103 views

Reference for context-free grammar for Martin-Löf type theory

Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?
user avatar
  • 11
10 votes
1 answer
749 views

Ambiguity of regular expressions

Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can ...
user avatar
  • 471
3 votes
1 answer
100 views

Conditioning Probability on a Language With Measure 0

Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
user avatar
4 votes
0 answers
74 views

Terminology for languages of pairs of words

I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this? I wrote "double language" first (but that doesn't sound right to me), then &...
user avatar
2 votes
0 answers
84 views

Necessary and sufficient condition for an infinite tree to be context-free

A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
user avatar
  • 193
4 votes
1 answer
451 views

Can we efficiently convert from NFA to smallest equivalent DFA?

Definitions For any automaton $X$, let $L(X)$ denote the language recognized by $X$. For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$. ...
user avatar
1 vote
1 answer
77 views

Definition of Rabin acceptance condition for omega automatons [closed]

I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left ...
user avatar
0 votes
1 answer
53 views

Reduction of a language to a shorter equivalent [closed]

I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language \begin{array}{l} L_{1}=A^{*} \cdot\{b\}-\left(A^{*} \cdot(A-\{a\}) \cdot A^{*} \cdot\...
user avatar
  • 119
5 votes
1 answer
133 views

Different definitions of grammar complexity

It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
user avatar
  • 411
5 votes
1 answer
91 views

Nonterminal descriptional complexity of regular languages

Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below. I am aware of an ...
user avatar
  • 411
7 votes
0 answers
100 views

Deciding whether DCFG is visibly pushdown

Is the following problem decidable? If so, what's the best algorithm known? Instance: a deterministic pushdown automaton $A$ Question: Does there exist (i) some partition of the alphabet into push, ...
user avatar
  • 907
3 votes
1 answer
124 views

how to define "correlation" between languages?

How does one define the concept of correlation between languages? Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this ...
user avatar
  • 291
12 votes
0 answers
181 views

Regular languages accepted by an automaton with at most one transition per letter

I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
user avatar
  • 7,455
3 votes
1 answer
142 views

Generalizations of Dyck languages?

The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and ...
user avatar
  • 907
2 votes
1 answer
152 views

What graphs on $\mathbb{N}$ can be encoded as regular languages?

Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
user avatar
1 vote
0 answers
29 views

Decidability of regular partition construction given its existence

Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$. If we know that $G$ is LL(...
user avatar
  • 111
2 votes
0 answers
17 views

Power of Hyperedge Replacement Grammars (HRGs)

Can HRGs generate languages which equal or include the following graph languages: All (bipartite) graphs of bounded degree All (bipartite) planar graphs of bounded degree All (bipartite) planar ...
user avatar
  • 101
5 votes
3 answers
356 views

Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given ...
user avatar
1 vote
1 answer
97 views

How to prove that Supremum preorder coincides with Hoare preorder?

Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$. I mean: Hoare ...
user avatar
5 votes
1 answer
187 views

Kolmogorov Complexity of a Decidable Language

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
user avatar
6 votes
2 answers
535 views

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
user avatar
7 votes
1 answer
228 views

Languages whose Parikh image is recognizable

Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By ...
user avatar
  • 1,947
3 votes
0 answers
93 views

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? (Quantum automata)

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
user avatar
8 votes
7 answers
1k views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
user avatar
  • 1,947
3 votes
1 answer
126 views

Embarrassingly Parallel: Formal Definition & Citation

I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where: ...
user avatar
10 votes
3 answers
891 views

Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
user avatar
  • 907
3 votes
0 answers
104 views

The number of words of length $n$ in a context-sensitive language

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$. What is known about $s_{L}(n)$? Note that it is known that $s_{L}(n)$ is either polynomial,...
user avatar
  • 347
3 votes
1 answer
111 views

Term for a set that is not immune

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...
user avatar
  • 133
0 votes
2 answers
205 views

Is the decidability of a language decidable? [closed]

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
user avatar
  • 291
1 vote
3 answers
435 views

what is a model of computation, mathematically? [closed]

Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...
user avatar
  • 291
0 votes
0 answers
49 views

Incompleteness and term extraction

Is there a formalization, which from a proof that a system includes enough arithmetic extracts an arithmetic sentence in the language of PA, which is not provable in the given system? Imagine the ...
user avatar
  • 723

1
2 3 4 5
9