Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms (1)

4
votes
1answer
81 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 ...
-5
votes
0answers
46 views

Is creativity computable?

Disclaimer - I am sorry if this question is too basic and non researchy for this forum, but I have been struggling to get a clear answer and this seems to be the place where I could get good leads. ...
0
votes
0answers
18 views

Converting a N-FSA with lambda-moves to a Mealy Machine

I would like to ask a few questions regarding Mealy Machines and N-FSA's with lambda-moves. How do we convert lambda-moves (empty-transitions) from a non-deterministic FSA when converting it into a ...
4
votes
1answer
143 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
93 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 ...
12
votes
3answers
276 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
350 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 ...
-1
votes
2answers
55 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 ...
0
votes
0answers
38 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.
19
votes
1answer
249 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 ...
9
votes
1answer
293 views

Are there non-constructive proofs of existence of “small” Turing machines / NFAs?

After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines ...
-1
votes
1answer
104 views

is determining an unknown CFL from intersection of two CFLs decidable?

this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it ...
8
votes
1answer
247 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 ...
0
votes
1answer
204 views

Theta functions of automata relations

Let $A,B$ be two automata over the same alphabet $\Sigma$; they are supposed to be complete, strongly connected DFAs. We denote by $._A$ (resp. $._B$) the action induced by $\Sigma^*$ over $Q(A)$, ...
4
votes
3answers
178 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 ...
5
votes
0answers
152 views

Data structures for Finite Automata

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
6
votes
0answers
116 views

Conjecture about two counters automata

I would like to prove (or disprove) the following conjecture: Conjecture: a two counter automata (2CA) cannot decide the following language: $L = \{ n \mid $ the ternary and binary representations ...
7
votes
2answers
135 views

A tool for minimal NFA computation

It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$. As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little ...
1
vote
1answer
60 views

On equivalence of NLBA and DLBA

Where I can find reference and documents on the work made for proving whether DLBA are equal NLBA nr not? What is the underlying problem? Why it is still an open question in TCS?
1
vote
1answer
215 views

What are good conferences for algorithms about finite automata?

I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties. Could you point out some ...
0
votes
2answers
461 views

Difference between infinite state machines and turing machines

Finite state machines (FSM) are strictly less powerful than turing machines (TM). But this is not the case with infinite state machines (ISM). For example, every TM can be embedded into some ISM. ...
3
votes
0answers
90 views

Concentration of Stationary Distribution on Random Directed Graphs

We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. ...
10
votes
2answers
195 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. ...
2
votes
0answers
60 views

WFSA over hyperreals

Are there any works where authors tried to define weighted finite state automata over hyperreals (or a similar object allowing for infinite and infinitesimal values) in an attempt to make automata ...
11
votes
2answers
306 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
60 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 ...
5
votes
1answer
93 views

Inverse of transducer compositions

Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an FSM transducer). These machines are closed under compositions. A composition of two GSMs $f(x)$ and $g(x)$ can be written ...
2
votes
1answer
123 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
79 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, ...
18
votes
2answers
542 views

Bounds on the size of the smallest NFA for L_k-distinct

Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal: $$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall ...
0
votes
1answer
95 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 ...
3
votes
0answers
66 views

Sub optimal regex equivalence

Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence ...
6
votes
0answers
179 views

Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability

A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we ...
-2
votes
1answer
139 views

Intersection between context-free and context-sensitive language decidability [closed]

I'm trying to find a formal proof of the following fact: Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ...
8
votes
2answers
172 views

2DFA that requires many states in equivalent DFA?

Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA? A two-way DFA (2DFA) is a deterministic finite-state ...
3
votes
0answers
88 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
67 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 ...
3
votes
0answers
84 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 ...
1
vote
4answers
210 views

Questions about regular languages and their sublanguages

I am interested in the following questions and would be grateful if anyone could give me hints or point me to articles: 1) Given a regular language $L$, what are its regular sublanguages $L'\subseteq ...
0
votes
1answer
105 views

Does every regular language contains a strictly locally testable language?

Let $L$ be an infinite regular language, then does there exists a strictly locally testable infinite language $P$ such that $P \subseteq L$?
1
vote
0answers
130 views

Finding self-similar homomorphisms of a FSM transducer

Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function ...
9
votes
0answers
165 views

Minimizing residual finite state automata

Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular ...
4
votes
1answer
86 views

When does a set of infixes determine a set of ($\omega$-) words

If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for ...
2
votes
1answer
133 views

Closure Properties of Locally Testable Language

Are locally testable languages closed under complementation? I guess yes, because when I can decide membership by sliding a window of size $k$ over the word and looking if the $k$-length words ...
10
votes
1answer
172 views

Can one-way alternating automata with one-counter recognize some unary non-regular languages?

One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ (Alternation by Chandra, Kozen, and Stockmeyer, 1981). By replacing a pushdown storage of a 1APDA with a ...
1
vote
0answers
87 views

Properties of the number of copies of an NFA in each state

For an NFA $A$ with $n$ states and a word $w$, we can associate an $n$-dimensional vector $v_w$ with entries in $\mathbb{N}\cup\{0\}$ denoting the number of copies of the NFA in each state after ...
4
votes
3answers
179 views

How to minimize a FSM transducer?

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...
1
vote
0answers
102 views

Learning about Nested Stack Automata

I want to learn about nested stack automata. However my efforts to find a suitable learning resource have so far been abortive: The Wikipedia article on nested stack automata is a stub. Alfred Aho's ...
-5
votes
1answer
204 views

Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent. 1. http://rubular.com/r/K9Hp9tU6px 2. http://rubular.com/r/N8VpoEcch4 EDIT: Forgot that + was ambiguous here! I want to prove that the ...
5
votes
0answers
105 views

Has a result of Book and Greibach on Quasi-Realtime languages been improved?

Quasi-realtime languages are defined as languages accepted by nondeterministic multitape Turing machines in quasi-real time. Ronald Book and Sheila Greibach have shown in their 1970 paper that every ...