Eine besondere Klasse von Sprachen: "kreisförmige" Sprachen. Ist es bekannt?

20

Definieren Sie die folgende Klasse von "zirkulären" Sprachen über ein endliches Alphabet Sigma. Tatsächlich gibt es den Namen bereits, um etwas anderes zu bezeichnen, das auf dem Gebiet des DNA-Computing verwendet wird. AFAICT, das ist eine andere Klasse von Sprachen.

Eine Sprache L Kreis iff für alle Wörter ist ww in Σ *Σ , haben wir:

ww gehört zu Lwenn und nur wenn für alle ganzen Zahlen k > 0k>0 , w kwk zu L. gehört

Ist diese Sprachklasse bekannt? Ich interessiere mich für die Kreissprachen, die auch regelmäßig sind, insbesondere für:

  • ein Name für sie, wenn sie bereits bekannt sind

  • Entscheidbarkeit des Problems, vorausgesetzt, ein Automat (insbesondere ein DFA), ob die akzeptierte Sprache der obigen Definition entspricht

Vincenzoml
quelle
1
Das ist eine sehr interessante Frage. Zwei verwandte Fragen: 1) Wenn wir eine reguläre Sprache L und ein zugehöriges DFA haben, können wir es kreisförmig machen? 2) Ist es bei einer gegebenen Sprache L so, dass circ (L) regelmäßig ist oder einige nette Eigenschaften hat?
Suresh Venkat
ps vielleicht ist das offensichtlich, aber warum denkst du, dass kreisförmige Sprachen eine Unterklasse der regulären Sprachen sind?
Suresh Venkat
3
@Suresh, ich denke, er definiert eine Sprache als zirkulär, wenn sie a) regelmäßig ist; b) genügt ein Verschluß Eigenschaft w L , n N : w nL . wL,nN:wnL
Peter Taylor
Crosspost in MO .
Hsien-Chih Chang 張顯 張顯
1
Vielleicht sollte der Dank nicht gepostet werden, aber dies war meine erste Frage und ich schätzte die Qualität der Kommentare, Antworten und Diskussionen sehr. Vielen Dank.
Vincenzoml

Antworten:

19

Im ersten Teil zeigen wir einen exponentiellen Algorithmus zur Bestimmung der Zirkularität. Im zweiten Teil zeigen wir, dass das Problem coNP-schwer ist. Im dritten Teil zeigen wir, dass jede Kreissprache eine Vereinigung von Sprachen der Form r + ist (hier könnte r der leere reguläre Ausdruck sein); Die Gewerkschaft ist nicht unbedingt unzusammenhängend. Im vierten Teil zeigen wir eine Kreissprache, die nicht als disjunkte Summe r + i geschrieben werden kann .r+rr+i

Bearbeiten: Einige Korrekturen wurden nach Marks Kommentaren eingefügt. Insbesondere meine früheren Behauptungen, dass die Zirkularität coNP-vollständig oder NP-hart ist, werden korrigiert.

Edit: Normalform von r i nach r + i korrigiertrir+i . Stellte eine "inhärent mehrdeutige" Sprache aus.


In Fortsetzung von Peter Taylors Kommentar erfahren Sie hier, wie Sie (äußerst ineffizient) entscheiden können, ob eine Sprache aufgrund ihres DFA zirkulär ist. Konstruieren Sie einen neuen DFA, dessen Zustände n- Tupel der alten Zustände sind. Dieser neue DFA führt n Kopien des alten DFA parallel aus.nn

Wenn die Sprache nicht zirkulär ist, gibt es ein Wort w, so dass wir, wenn wir es wiederholt durch den DFA laufen lassen, beginnend mit dem Anfangszustand s 0 , die Zustände s 1 , ... , s n erhalten, so dass s 1 nur eins akzeptiert der anderen akzeptiert nicht (wenn alle akzeptieren , muss die Sequenz s 0 , ... , s n zyklisch ablaufen, damit w immer in der Sprache ist). Mit anderen Worten, wir haben einen Pfad von s 0 , ... , s nws0s1,,sns1s0,,snw - 1 zu ss0,,sn1 1 , , s n, wobei s 1 akzeptiert, aber einer der anderen nicht akzeptiert. Umgekehrt kann dies nicht passieren, wenn die Sprache zirkulär ist.s1,,sns1

Daher haben wir das Problem auf einen einfachen gerichteten Erreichbarkeitstest reduziert (überprüfen Sie einfach alle möglichen "schlechten" n- Tupel).n


Das Problem der Zirkularität ist coNP-schwer. Angenommen , wir haben ein 3SAT - Instanz mit gegebenen n Variablen x und m Klauseln C 1 , ... , C m . Wir können annehmen, dass n = m (Dummy-Variablen hinzufügen) und n Primzahl ist (andernfalls finden wir eine Primzahl zwischen n und 2 n)nx⃗ mC1,,Cmn=mnn2n mit AKS-Primalitätstests finden und Dummy-Variablen und -Klauseln hinzufügen).

Betrachten Sie die folgende Sprache: "Die Eingabe hat nicht die Form x 1x n, wobei x i eine befriedigende Zuweisung für C i ist ". Es ist einfach, einen O ( n 2 ) -DFA für diese Sprache zu erstellen. Wenn die Sprache nicht zirkulär ist, gibt es ein Wort w in der Sprache, von dem eine Kraft nicht in der Sprache liegt. Da die einzigen Wörter, die nicht in der Sprache sind, die Länge n 2 haben , muss w die Länge 1 oder n 1 habenx⃗ 1x⃗ nx⃗ iCiO(n2)wn2w1n . Wenn es lang ist1stattdessen w n (es ist immer noch in der Sprache), so dass w in der Sprache ist und w n nicht in der Sprache ist. Die Tatsache, dass w n nicht in der Sprache ist, bedeutet, dass w eine zufriedenstellende Aufgabe ist.wnwwnwnw

Umgekehrt wird jede befriedigende Zuweisung zu einem Wort übersetzt, das die Unrundheit der Sprache beweist: Die befriedigende Zuweisung w gehört zur Sprache, w n jedoch nicht. Daher ist die Sprache zirkulär, wenn die 3SAT-Instanz nicht erfüllt werden kann.wwn


In diesem Teil diskutieren wir eine normale Form für Kreissprachen. Betrachten wir einige DFA für eine Kreis Sprache L . Eine Folge C = C 0 , ... ist real, wenn C 0 = s (der Anfangszustand) ist, alle anderen Zustände akzeptieren, und C i = C j impliziert C i + 1 = C j + 1 . Somit ist jede reale Sequenz schließlich periodisch, und es gibt nur endlich viele reale Sequenzen (da der DFA endlich viele Zustände hat).LC=C0,C0=sCi=CjCi+1=Cj+1

We say that a word behaves according to CC if the word takes the DFA from state cici to state ci+1ci+1, for all ii. The set of all such words E(C)E(C) is regular (the argument is similar to the first part of this answer). Note that E(C)E(C) is a subset of LL.

Given a real sequence CC, define CkCk to be the sequence Ck(t)=C(kt)Ck(t)=C(kt). The sequence CkCk is also real. Since there are only finitely many different sequences CkCk, the language D(C)D(C) which is the union of all E(Ck)E(Ck) is also regular.

We claim that D(C)D(C) has the property that if x,yD(C)x,yD(C) then xyD(C)xyD(C). Indeed, suppose that xCkxCk and yClyCl. Then xyCk+lxyCk+l. Thus D(C)=D(C)+D(C)=D(C)+ can be written in the form r+r+ for some regular expression rr.

Every word ww in the language corresponds to some real sequence CC, i.e. there exists a real sequence CC that ww behaves according to. Thus LL is the union of D(C)D(C) over all real sequence CC. Therefore every circular language has a representation of the form r+ir+i. Conversely, every such language is circular (trivially).


Consider the circular language LL of all words over a,ba,b that contain either an even number or aa's or an even number of bb's (or both). We show that it cannot be written as a disjoint sum r+ir+i; by "disjoint" we mean that r+ir+j=r+ir+j=.

Let NiNi be the size of the some DFA for r+ir+i, and N>maxNiN>maxNi be some odd integer. Consider x=aNbN!x=aNbN!. Since xLxL, xr+ixr+i for some ii. By the pumping lemma, we can pump a prefix of xx of length at most NN. Thus r+ir+i generates z=aN!bN!z=aN!bN!. Similarly, y=aN!bNy=aN!bN is generated by some r+jr+j, which also generates zz. Note that ijij since xyLxyL. Thus the representation cannot be disjoint.

Yuval Filmus
quelle
There seem to be a number of errors here. You're reducing from UNSAT, not SAT, so you're showing it's coNP-hard. What's your polynomial time witness for (non)-membership?
Mark Reitblatt
"Since the only words not in the language have length n2n2" Shouldn't that be nmnm?
Mark Reitblatt
I don't think it's "trivially in coNP". At least, it's not trivially obvious to me. The "obvious" certificate would be a string ll in the language, and a power kk such that lklk isn't in the language. But it's not immediately obvious to me why such a word must be polynomially-sized. Maybe it's by a simple fact of automata theory that I'm overlooking.
Mark Reitblatt
An even more serious apparent flaw is that you jump from each clause being satisfiable individually to the whole formula being satisfiable. Unless I am misreading, of course.
Mark Reitblatt
I agree that it's not clear that circularity is in coNP. On the other hand, I see no problems in the rest of the argument (now that I've put n=mn=m). If each clause is satisfied by the same assignment, then the 3SAT instance is satisfied by this assignment.
Yuval Filmus
17

Here are some papers that discuss these languages:

Thierry Cachat, The power of one-letter rational languages, DLT 2001, Springer LNCS #2295 (2002), 145-154.

S. Hovath, P. Leupold, and G. Lischke, Roots and powers of regular languages, DLT 2002, Springer LNCS #2450 (2003), 220-230.

H. Bordihn, Context-freeness of the power of context-free languages is undecidable, TCS 314 (2004), 445-449.

Jeffrey Shallit
quelle
6

@Dave Clarke, L = a*|b* would be circular, but L* would be (a|b)*.

In terms of decidability, a language LL is circular if there is an LL such that LL is the closure under + of LL or if it is a finite union of circular languages.

(I'm dying to redefine "circular" replacing your >> with . It simplifies things a lot. We can then characterise the circular languages as those for which there exists a NDFA whose starting state has only epsilon-transitions to accepting states and has an epsilon-transition to each accepting state).

Peter Taylor
quelle
You are right. I've removed my incorrect post.
Dave Clarke
Regarding adaption with : I am thinking that a minimal DFA should always have exactly one accepting state, namely the start state. Maybe more accepting states can happen, but then they need an εε-transition to the start state.
Raphael
1
@Raphael, consider again L = a*|b*. A DFA whose start state is the only accepting state and which accepts a and b must accept (a|b)*.
Peter Taylor
On the question of decidability, again: suppose you have a DFA with nn states of which nana are accepting. Suppose it accepts a word ww, and also accepts w2w2, w3w3, ..., wna+1wna+1. Then it accepts wxwx for x>0x>0. (Proof is a straightforward application of the pigeonhole principle). If it's possible to show that the minimal (minimising |w||w|) counterexample (ww, xx) to the circularity of the language accepted by the DFA has length bounded by a function of nn then brute force testing is possible. I suspect that |w|<=n+1|w|<=n+1, but I haven't proved it.
Peter Taylor
To follow up on @Raphael's idea above. The idea of start state = only accept state is wrong for this problem, but it does capture some interesting property. When M is a minDFA, the start state is the only accept state if and only if L(M) is the Kleene star of a prefix-free language. This is one of my favorite DFA trivia tidbits and thus I am quick to share it! ;)
mikero
5

Edit: A complete (simplified) PSPACE-completeness proof appears below.

Two updates. First, the normal form described in my other answer appears already in a paper by Calbrix and Nivat titled Prefix and period languages of rational ωω-langauges, unfortunately not available online.

Second, deciding whether a language is circular given its DFA is PSPACE-complete.

Circularity in PSPACE. Since NPSPACE=PSPACE by Savitch's theorem, it is enough to give an NPSPACE algorithm for non-circularity. Let A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F) be a DFA with |Q|=n|Q|=n states. The fact that the syntactic monoid of L(A)L(A) has size at most nnnn implies that if L(A)L(A) is not circular then there is a word ww of length at most nnnn such that wL(A)wL(A) but wkL(A)wkL(A) for some knkn. The algorithm guesses ww and computes δw(q)=δ(q,w)δw(q)=δ(q,w) for all qQqQ, using O(nlogn)O(nlogn) space (used to count up to nnnn). It then verifies that δw(q0)Fδw(q0)F but δ(k)wFδ(k)wF for some knkn.

Circularity is PSPACE-hard. Kozen showed in his classic 1977 paper Lower bounds for natural proof systems that it is PSPACE-hard to decide, given a list of DFAs, whether the intersection of the languages accepted by them is empty. We reduce this problem to circularity. Given binary DFAs A1,,AnA1,,An, we find a prime p[n,2n]p[n,2n] and construct a ternary DFA AA accepting the language L(A)=¯{2w12w22wp:wiL(A1+(imodn))}.

L(A)={2w12w22wp:wiL(A1+(imodn))}¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯.
(With some more effort, we can make AA binary as well.) It is not difficult to see (using the fact that p is prime) that L(A) is circular if and only if the intersection L(A1)L(An) is empty.
Yuval Filmus
quelle
0

Every sL of length p>0 can be written as xyiz where x=z=ϵ , y=wϵ . It's obvious that |xy|p and |y|=|w|>0. It follows that the language is regular for non-empty inputs, by the pumping lemma.

For w=ϵ , the definition holds, since a NDFA that accepts the empty string will also accept any number of empty strings.

The union of the above languages is the language L and since regular languages are closed under union, it follows that every circular language is regular.

By Rice's theorem, CIRCULARITY/TM is undecidable. The proof is similar to regularity.

chazisop
quelle
1
The pumping lemma is a necessary, but not sufficient, condition for regularity. In particular, there are nonregular languages satisfying the pumping condition. Also, Rice's theorem would say that {M|L(M) is circular} is undecidable. This does not mean that {D|L(D) is circular} is undecidable (where D is a DFA, M a TM)! For instance, emptiness testing for DFAs is decidable, while emptiness testing for TMs is not.
alpoge
1
Here's a non-computable circular language. Let D={0x1:xR}, where R is some non-computable language (e.g. codes of halting TMs). Then D is circular but clearly non-computable (an oracle for D can be used to decide R).
Yuval Filmus
2
@Peter, have you read this answer? It was trying to prove that any circular language (without the condition of regularity) is regular.
Yuval Filmus
1
@Yuval, my mistake. @chazisop, the pumping lemma is useful for proving non-regularity of languages, but not regularity. (Besides, the assertion of your first sentence reduces to "Every sL of length p>0 can be written as yi where yϵ", which is clearly false).
Peter Taylor
1
Yes, I use CIRCULARITY/TM to refer to this. CIRCULARITY/DFA is probably decidable.
chazisop