In the course of my research (condensed matter physics stuff), I stumbled over the following concept:

The class of regular languages can be defined via finite state machines (FSM): A language $L$ is regular iff there is an FSM which accepts $L$. Clearly every finite language is regular.

I am interested in the following (larger) class of languages (call it $\mathcal{L}^?$) over some finite alphabet $\Sigma$ with relaxed conditions:

A language $L$ is in $\mathcal{L}^?$ $:\Leftrightarrow$

There is a sequence of FSMs $(M_n)_{n\in\mathbb{N}}$ such that

  1. $w\in L\,\Leftrightarrow\,$ $M_{|w|}(w)$ accepts
  2. $|M_n|\leq \operatorname{Poly}(n)$

Here $|w|$ denotes the length of word $w$ and $|M|$ is the size of the FSM $M$, i.e., its number of states.

Obviously all languages $L\subseteq \Sigma^\ast$ are included if one drops the second requirement, as the sublanguages $L_n\subseteq L$ of words with fixed length $n$ are finite. But for a generic language $L_n$ with fixed length words, the minimal accepting FSA has a size exponentially growing in $n$ (is this correct? I sketched just a naive counting argument...).

As I'm no computer scientist, I was wondering whether this concept is already known in automata theory / computability theory (and if so, how it is called). Due to my lack of expertise, I just do not know where to start.

I would be very happy if you could ...

  • either provide a pointer to the relevant topic of automata theory (terms I have to look for, relevant publications)
  • or give an alternative characterization of this class (maybe it's just equivalent to one of the well-known language classes?)

Thank you in advance!

  • 1
    $\begingroup$ The relevant area is computational complexity, though I've never heard of this particular circuit model. Your class is a subset of L/poly, though probably much smaller. $\endgroup$ – Yuval Filmus Sep 24 '14 at 15:17
  • 1
    $\begingroup$ the problem is probably fairly closely related to counting isomorphisms of graphs of given sizes.... yes this question has been asked before, Languages recognized by polynomial-size DFAs (cstheory.se) and is apparently mostly open & studied only somewhat peripherally $\endgroup$ – vzn Sep 24 '14 at 22:52
  • $\begingroup$ @YuvalFilmus: +1 for pointing to L/poly. I am going to read about it. $\endgroup$ – NcLang Sep 25 '14 at 5:50
  • $\begingroup$ @vzn: +1 for providing the reference to cstheory.se. Seems there is work to do for the theoretical computer scientists, thought. I'll have a look at the (few) references suggested there. $\endgroup$ – NcLang Sep 25 '14 at 5:54
  • $\begingroup$ @NcLang : $\:$ Are FSMs allowed to go backwards over the input? $\;\;\;\;$ $\endgroup$ – user12859 Sep 26 '14 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.