formal languages, grammars, automata theory

learn more… | top users | synonyms (2)

4
votes
1answer
44 views

Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition. http://www.sciencedirect.com/science/article/pii/030439759190180A Scott's algorithm on building ...
8
votes
2answers
103 views

Separating lists of words

There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, ...
1
vote
0answers
117 views

Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
3
votes
2answers
98 views

Translation of context-free parsing into SAT

Is there a published algorithm for translating a context-free parsing problem into SAT? That is, an algorithm that translates a context-free grammar and an input string into a set clauses that is ...
11
votes
2answers
192 views

Vector Addition Systems with finite “obstacles”

A Vector Addition System (VAS) is a finite set of actions $A \subset \mathbb{Z}^d$. $\mathbb{N}^d$ is the set of markings. A run is a non-empty word of markings $m_0 m_1\dots m_n$ s.t. $\forall i \in ...
9
votes
2answers
117 views

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" ...
7
votes
1answer
94 views

Extensional characterization of non-deterministic finite state transductions

I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of ...
5
votes
1answer
142 views

Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
5
votes
2answers
104 views

Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
0
votes
0answers
105 views

Is there an algorithm to find whether 2 combinators form a Turing-complete system?

It is known that K = (λx.(λy.x)) and S = (λx.(λy.(λz.((x z) (y z))))) define a turing complete system, and we know procedures to ...
10
votes
1answer
541 views

Decide the existence of a string homomorphism

Consider the following problem: Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y. It is easy to show that this problem is in $NP$. Are there other ...
14
votes
2answers
264 views

Does XOR automata (NXA) for finite languages benefit from cycles?

A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA ...
5
votes
2answers
206 views

Bounds on size of self-concatenation of Finite Languages

Given a finite language $L$ with $|L|$ number of elements, what is $|L^i|$ (the language $L$ concatenated with itself $i$ times)? If there is no exact result, is there an upper/lower bound? Define ...
5
votes
1answer
124 views

What is the importance of linear languages?

What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have ...
3
votes
0answers
129 views

Restricted-Input Automaton

In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$. All of the related concepts are then ...
10
votes
0answers
202 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
5
votes
1answer
137 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
6
votes
1answer
148 views

Bounds on the size of NFA for $r$-skip $k$-distinct language

This question is about an extension of a language discussed in this question. We define the $r$-skip $k$-distinct language as follows: $$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | ...
0
votes
0answers
100 views

In what complexity classes other than $NP$ are these problems related to unary languages?

If I remember correctly saw this reduction in a paper can't find at the moment. Consider the following NP-complete variation of the Subset Sum problem. Given a set of positive integers ...
4
votes
1answer
213 views

What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$. ...
6
votes
2answers
125 views

Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$. Are any known results about whether deterministic context-free languages are closed under this operation, or ...
20
votes
3answers
291 views

Complexity of intersection of regular languages as context-free grammars

Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?
2
votes
1answer
256 views

Natural examples of context-sensitive languages from practice

I am looking for natural examples of context-sensitive languages from practice. For example, reasonable answers could include grammar syntax of a programming language, or encoding of certain ...
1
vote
0answers
63 views

Can the definition of ambiguity of CFG be extended to CSG?

Usually,ambiguity of grammar is defined for constext-free languages and grammars,sometime it is extended to indexed languages and grammar,but the extension of definition of the definition is same ...
13
votes
4answers
367 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
15
votes
1answer
367 views

Can constant ambiguity reduce the state complexity of a regular languages?

We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths. If automaton $M$ is constantly ...
8
votes
1answer
134 views

Asymptotic density of ambiguous context-free grammars (CFGs)

What is the ratio of ambiguous CFGs to all CFGs? Since both sets are countably infinite the ratio is not well-defined. But what about the asymptotic density: $$\lim_{n \mapsto \infty}\frac {\# ...
-1
votes
2answers
80 views

Looking for menu-driven coding editor based on a programming language state machine [closed]

I'd like to know whether an application development environment exists that uses a menu-driven coding editor that employs a programming language state machine. This would mean that commands, variable ...
4
votes
1answer
462 views

What are the relationship and difference between ambiguous grammars and non-deterministic ones?

Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false: there are non-deterministic unambiguous CFGs ...
0
votes
0answers
55 views

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form? I cannot find an reference.
20
votes
1answer
298 views

Languages recognized by polynomial-size DFAs

For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$. I am interested in ...
8
votes
1answer
232 views

Reversible Turing tarpits?

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ...
8
votes
1answer
297 views

Lower bound for NFA accepting 3 letter language

Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from ...
4
votes
3answers
198 views

Regular languages under change of encoding

Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$. Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other ...
12
votes
2answers
194 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols ...
1
vote
2answers
114 views

Tool for specifying operational semantics for given formally specified programming language

I am trying to translate code from one programming language into another (to be specific - from RuleML to Drools, but other pairs can be expected as well) and it would be nice to know - whether there ...
11
votes
2answers
324 views

Why is linearizability a safety property and why are safety properties closed sets?

In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace ...
5
votes
2answers
150 views

Higher order Quines - when do super Quines exist?

The normal Quine - a program that prints its own code - is a special case of an n-Quine. An n-Quine is a program that prints code for a different program that after n iterations of printing and ...
16
votes
0answers
211 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
10
votes
2answers
214 views

The number of states of local automata

A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local for $k > 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. ...
11
votes
2answers
342 views

How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA). A NFA is called $unambiguous$ if every word $w\in \Sigma^*$ has at most one accepting path. This ...
4
votes
1answer
70 views

The polynomial languages and ordered syntactic monoids

A polynomial language is a languge which could be represented as the finite union of languages of the form: $$ A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X $$ Such an ...
2
votes
1answer
174 views

Computing the Syntactic Congruence

The syntactic monoid of a language $L \subseteq X^*$ is defined as the monoid obtained from the congruence relation $$ u\ \tilde{}\ v \ \mbox{ iff }\ \forall x,y \in X^* : xuy \in L \leftrightarrow ...
3
votes
0answers
102 views

Deciding whether a binary multiplicity automaton has empty language

Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
0
votes
1answer
131 views

Adherence of languages and the Dyck language

Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of ...
1
vote
1answer
65 views

Assessing complexity of a language using subset relations

What makes a language hard in a computational sense is neither simply that it contains very few words(e.g. is finite) or that it contains a lot of words(e.g. is infinte) but rather an intricate ...
3
votes
0answers
95 views

Transfering properties from subsets of $X^*$ to subsets of $X^{\omega}$ by using the topology induces by Cantor space

A language $L \subseteq X^*$ is non-counting of order $n > 0$ iff for all $u,v, w \in X^*$ $$ uv^nw \in L \Leftrightarrow uv^{n+1} w \in L. $$ A $\omega$-language (set of infinite sequences) $L ...
0
votes
1answer
68 views

Difference between locally testable and it's boolean closure

A language $L$ is called i) locally testable in the strict sense iff there exists $P, S, I \subseteq X^*$ such that $$ w \in L \mbox{ iff } pref^k(w) \in P, suffix^k(w) \in S, infix^k(w) \subseteq ...
14
votes
1answer
257 views

Can a two counters machine decide $n^2$?

Can a standard two counters ($c_1,c_2$) machine with the following instructions: ...
3
votes
0answers
91 views

Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$: $$ L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in ...