151:
74:
53:
22:
399:
Naive question: In "String substitution" we read that the a substitution "... is a mapping f that maps letters ... to languages"; but in "String homomorphism" we read that a homomorphism "... is a string substitution such that each letter is replaced by a single string". Now strings are categorically
678:
I know a bit about the history of formal language theory, and was able to track the notion of the quotient of formal languages, as defined in the
Hopcroft/Ullman 1979 book, back to a paper by Ginsburg and Spanier (J. ACM, 1693). They state that the notion of quotients (of languages, not of strings)
694:
Probably, the HTML comment was inserted by me, when I tried to obtain sources for all the definitions. I agree with your suggestion. In addition, we should add your JACM 1963 reference (I understood that
Ginsburg and Spanier gave the same definition as Hopcroft.Ullman.1979, right?). Via ACM and
679:
was investigated by the "SHARE Theory of
Information Handling Committee" at the time. I would suggest to keep the Hopcroft/Ullman definition of quotients (of languages) and remove the deviating, unsourced definition of quotient (of strings, then extended to quotients of languages).
172:
750:, there is an uppercase form of the letter Ă, namely áş. There is nothing theoretically wrong with the example, but the wording "no uppercase char available" might be rephrased to reflect this fact. (It's funny how using examples from ordinary languages often backfires.)
717:
The following results on the quotient of context-free languages (CFL) are shown: (1) It is recursively unsolvable to determine for arbitrary CFL whether the quotient of one by another is a CFL. (2) If either set is regular and the other is a CFL, then the quotient is a
599:
449:
An example of string substitution occurs in regular languages, which are closed under string substitution. That is, if the letters of a regular language are substituted by other regular languages, the result is still a regular
196:
336:
497:
253:
191:
778:
124:
114:
419:
I agree. Hopcroft and Ullman, after having defined substitutions and strings (on p.60) in the same way as in the article, add the following remark: "We generally take
660:
783:
773:
90:
298:
674:
This definition deviates from
Hopcroft.Ullman.1979, as remarked below. I guess the former doesn't have widespread use, if it has a source at all.
272:
137:
81:
58:
361:
755:
474:) says, even regular tree languages are. However, I didn't check whether its notion of inverse homomorphism its similar to the one here.
244:
225:
470:
Another question: aren't regular (string) languages also closed w.r.t. inverse string homomorphisms? The TATA-Book (reference see
751:
317:
404:
as something that maps letters to languages and also as something that maps letters to strings. It seems confusing at best. --
602:
what I don't know: does that mean 'abc' is the only word, so I might shorten the word but not mix it/ make it longer? thanks
427:) to be the string itself, rather than the set containing that string." A similar remark should be added in the article. -
700:
282:
163:
33:
292:
206:
731:
479:
432:
327:
89:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
467:
I'll think about an example for that. Meanwhile, I hope that the examples I added are helpful and not too trivial.
354:
594:{\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}
21:
727:
475:
457:
428:
263:
39:
471:
409:
182:
684:
453:
234:
86:
637:
494:(I came here to get an idea what 'prefix-closed assertion' could mean) The example says
308:
150:
173:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
767:
670:
This is followed by the following comment, which is only visible in the HTML source:
400:
distinct from languages (aren't they?), so surely a substitution can't be defined
680:
405:
215:
759:
735:
688:
483:
461:
436:
413:
73:
52:
747:
742:
The example of substitution using Ă ~ SS is not entirely correct
291:
Find pictures for the biographies of computer scientists (see
15:
395:
Substitution: maps to languages or to strings or either?
666:
on the right hand side, the result is the empty string.
527:
640:
500:
723:
Maybe you can help to resolve some of the remaining
85:, a collaborative effort to improve the coverage of
699:Seymour Ginsburg and Edwin H. Spanier (Oct 1963).
654:
593:
197:Computer science articles needing expert attention
337:WikiProject Computer science/Unreferenced BLPs
634:, from the right hand side. It is denoted as
8:
254:Computer science articles without infoboxes
192:Computer science articles needing attention
19:
158:Here are some tasks awaiting attention:
132:
47:
644:
639:
526:
499:
779:Mid-importance Computer science articles
49:
99:Knowledge:WikiProject Computer science
784:WikiProject Computer science articles
774:Start-Class Computer science articles
701:"Quotients of Context-Free Languages"
695:Researchgate, I found this bib.data:
102:Template:WikiProject Computer science
7:
79:This article is within the scope of
626:is the truncation of the character
472:Regular_tree_grammar#External_links
38:It is of interest to the following
273:Timeline of computing 2020âpresent
14:
299:Computing articles needing images
149:
72:
51:
20:
119:This article has been rated as
662:. If the string does not have
545:
539:
1:
437:17:59, 19 February 2014 (UTC)
414:12:22, 19 February 2014 (UTC)
353:Tag all relevant articles in
93:and see a list of open tasks.
362:WikiProject Computer science
138:WikiProject Computer science
82:WikiProject Computer science
293:List of computer scientists
800:
736:08:46, 16 April 2018 (UTC)
689:20:36, 15 April 2018 (UTC)
462:21:05, 22 March 2013 (UTC)
125:project's importance scale
355:Category:Computer science
131:
118:
105:Computer science articles
67:
46:
760:09:15, 3 June 2023 (UTC)
484:15:52, 25 May 2013 (UTC)
452:What is the reference?
357:and sub-categories with
752:Lasse Hillerøe Petersen
490:Prefix example question
656:
595:
447:What does this mean?
318:Computer science stubs
28:This article is rated
657:
596:
638:
498:
136:Things you can help
655:{\displaystyle s/a}
443:String substitution
705:Journal of the ACM
652:
610:The article says:
591:
531:
34:content assessment
530:
392:
391:
388:
387:
384:
383:
380:
379:
376:
375:
791:
728:Jochen Burghardt
712:
661:
659:
658:
653:
648:
600:
598:
597:
592:
590:
586:
532:
528:
525:
521:
476:Jochen Burghardt
429:Jochen Burghardt
366:
360:
235:Computer science
164:Article requests
153:
146:
145:
133:
107:
106:
103:
100:
97:
96:Computer science
87:Computer science
76:
69:
68:
63:
59:Computer science
55:
48:
31:
25:
24:
16:
799:
798:
794:
793:
792:
790:
789:
788:
764:
763:
744:
698:
636:
635:
618:of a character
608:
555:
551:
511:
507:
496:
495:
492:
445:
397:
372:
369:
364:
358:
346:Project-related
341:
322:
303:
277:
258:
239:
220:
201:
177:
104:
101:
98:
95:
94:
61:
32:on Knowledge's
29:
12:
11:
5:
797:
795:
787:
786:
781:
776:
766:
765:
743:
740:
739:
738:
721:
720:
719:
676:
675:
668:
667:
651:
647:
643:
630:in the string
622:from a string
616:right quotient
607:
606:Right Quotient
604:
601:
589:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
554:
550:
547:
544:
541:
538:
535:
524:
520:
517:
514:
510:
506:
503:
491:
488:
487:
486:
468:
444:
441:
440:
439:
396:
393:
390:
389:
386:
385:
382:
381:
378:
377:
374:
373:
371:
370:
368:
367:
350:
342:
340:
339:
333:
323:
321:
320:
314:
304:
302:
301:
296:
288:
278:
276:
275:
269:
259:
257:
256:
250:
240:
238:
237:
231:
221:
219:
218:
212:
202:
200:
199:
194:
188:
178:
176:
175:
169:
157:
155:
154:
142:
141:
129:
128:
121:Mid-importance
117:
111:
110:
108:
91:the discussion
77:
65:
64:
62:Midâimportance
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
796:
785:
782:
780:
777:
775:
772:
771:
769:
762:
761:
757:
753:
749:
741:
737:
733:
729:
725:
722:
716:
711:(4): 487â492.
710:
706:
702:
697:
696:
693:
692:
691:
690:
686:
682:
673:
672:
671:
665:
649:
645:
641:
633:
629:
625:
621:
617:
613:
612:
611:
605:
603:
587:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
552:
548:
542:
536:
533:
522:
518:
515:
512:
508:
504:
501:
489:
485:
481:
477:
473:
469:
466:
465:
464:
463:
459:
455:
451:
442:
438:
434:
430:
426:
422:
418:
417:
416:
415:
411:
407:
403:
394:
363:
356:
352:
351:
349:
347:
343:
338:
335:
334:
332:
330:
329:
324:
319:
316:
315:
313:
311:
310:
305:
300:
297:
294:
290:
289:
287:
285:
284:
279:
274:
271:
270:
268:
266:
265:
260:
255:
252:
251:
249:
247:
246:
241:
236:
233:
232:
230:
228:
227:
222:
217:
214:
213:
211:
209:
208:
203:
198:
195:
193:
190:
189:
187:
185:
184:
179:
174:
171:
170:
168:
166:
165:
160:
159:
156:
152:
148:
147:
144:
143:
139:
135:
134:
130:
126:
122:
116:
113:
112:
109:
92:
88:
84:
83:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
746:As noted on
745:
724:
714:
708:
704:
677:
669:
663:
631:
627:
623:
619:
615:
609:
493:
448:
446:
424:
420:
401:
398:
345:
344:
328:Unreferenced
326:
325:
307:
306:
281:
280:
262:
261:
243:
242:
224:
223:
205:
204:
181:
180:
162:
161:
120:
80:
40:WikiProjects
454:Deltahedron
30:Start-class
768:Categories
726:, too? -
715:ABSTRACT:
450:language.
216:Computing
264:Maintain
207:Copyedit
245:Infobox
183:Cleanup
123:on the
681:Hermel
226:Expand
36:scale.
529:then
309:Stubs
283:Photo
140:with:
756:talk
732:talk
718:CFL.
685:talk
614:The
534:Pref
480:talk
458:talk
433:talk
410:talk
406:Bmcm
402:both
115:Mid
770::
758:)
734:)
713:â
709:10
707:.
703:.
687:)
557:Îľ
537:âĄ
482:)
460:)
435:)
412:)
365:}}
359:{{
754:(
748:Ă
730:(
683:(
664:a
650:a
646:/
642:s
632:s
628:a
624:s
620:a
588:}
584:c
581:b
578:a
575:,
572:b
569:a
566:,
563:a
560:,
553:{
549:=
546:)
543:L
540:(
523:}
519:c
516:b
513:a
509:{
505:=
502:L
478:(
456:(
431:(
425:a
423:(
421:h
408:(
348::
331::
312::
295:)
286::
267::
248::
229::
210::
186::
167::
127:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
