nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

How to Prove that a Language Is Regular or Star-Free?

verfasst von : Jean-Éric Pin

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This survey article presents some standard and less standard methods used to prove that a language is regular or star-free.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Recompression: Technique for Word Equations and Compressed Data

Nächstes Kapitel Deciding Classes of Regular Languages: The Covering Approach

Let M and N be monoids. We say that M divides N if there is a submonoid R of N and a monoid morphism that maps R onto M.

Bala, S.: Complexity of regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms. Theory Comput. Syst. 39(1), 137–163 (2006)MathSciNetMATHCrossRef

Berstel, J.: Transductions and Context-Free Languages. Teubner (1979)

Berstel, J., Boasson, L., Carton, O., Petazzoni, B., Pin, J.-É.: Operations preserving recognizable languages. Theor. Comput. Sci. 354, 405–420 (2006)MATHCrossRef

Bertoni, A., Mereghetti, C., Palano, B.: Quantum computing: 1-way quantum automata. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 1–20. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45007-6_1CrossRef

Bovet, D.P., Varricchio, S.: On the regularity of languages on a binary alphabet generated by copying systems. Inform. Process. Lett. 44(3), 119–123 (1992)MathSciNetMATHCrossRef

Bucher, W., Ehrenfeucht, A., Haussler, D.: On total regulators generated by derivation relations. Theor. Comput. Sci. 40(2–3), 131–148 (1985)MathSciNetMATHCrossRef

Büchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6, 66–92 (1960)MathSciNetMATHCrossRef

Büchi, J.R.: Regular canonical systems. Arch. Math. Logik Grundlagenforsch. 6, 91–111 (1964) (1964)

Carton, O.: Langages formels, calculabilité et complexité. Vuibert (2008)

10.

Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Inform. Comput. 176, 51–76 (2002)MathSciNetMATHCrossRef

11.

Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971)MATH

12.

D’Alessandro, F., Varricchio, S.: Well quasi-orders in formal language theory. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 84–95. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85780-8_6MATHCrossRef

13.

De Luca, A., Varricchio, S.: Finiteness and Regularity in Semigroups and Formal Languages. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-642-59849-4CrossRef

14.

Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theor. Comput. Sci. 27(3), 311–332 (1983)MathSciNetMATHCrossRef

15.

Ehrenfeucht, A., Parikh, R., Rozenberg, G.: Pumping lemmas for regular sets. SIAM J. Comput. 10(3), 536–541 (1981)MathSciNetMATHCrossRef

16.

Ehrenfeucht, A., Rozenberg, G.: On regularity of languages generated by copying systems. Discrete Appl. Math. 8(3), 313–317 (1984)MathSciNetMATHCrossRef

17.

Eiter, T., Gottlob, G., Gurevich, Y.: Existential second-order logic over strings. J. ACM 47(1), 77–131 (2000)MathSciNetMATHCrossRef

18.

Eiter, T., Gottlob, G., Schwentick, T.: Second-order logic over strings: regular and non-regular fragments. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol. 2295, pp. 37–56. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46011-X_4CrossRef

19.

Eiter, T., Gottlob, G., Schwentick, T.: The model checking problem for prefix classes of second-order logic: a survey. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of Logic and Computation. LNCS, vol. 6300, pp. 227–250. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15025-8_13MATHCrossRef

20.

Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98, 21–51 (1961)MathSciNetMATHCrossRef

21.

Hartmanis, J.: Computational complexity of one-tape Turing machine computations. J. Assoc. Comput. Mach. 15, 325–339 (1968)MathSciNetMATHCrossRef

22.

Hofbauer, D., Waldmann, J.: Deleting string rewriting systems preserve regularity. Theor. Comput. Sci. 327(3), 301–317 (2004)MathSciNetMATHCrossRef

23.

Hopcroft, J.E., Ullman, J.D.: Introduction To Automata Theory, Languages, And Computation. Addison-Wesley Publishing Co., Reading (1979). Addison-Wesley Series in Computer Science

24.

Jaffe, J.: A necessary and sufficient pumping lemma for regular languages. SIGACT News 10(2), 48–49 (1978)MathSciNetMATHCrossRef

25.

Kamp, J.: Tense Logic and the Theory of Linear Order. Ph.D. thesis, University of California, Los Angeles (1968)

26.

Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956). Ann. Math. Stud. 34

27.

Kosaraju, S.R.: Regularity preserving functions. SIGACT News 6(2), 16–17 (1974). Correction to “Regularity preserving functions”, SIGACT News 6(3), (1974), p. 22CrossRef

28.

Kozen, D.: On regularity-preserving functions. Bull. Europ. Assoc. Theor. Comput. Sci. 58, 131–138 (1996). Erratum: on regularity-preserving functions. Bull. Europ. Assoc. Theor. Comput. Sci. 59, 455 (1996)MATH

29.

Kozen, D.C.: Automata and computability. Undergraduate Texts in Computer Science. Springer, New York (1997). https://doi.org/10.1007/978-3-642-85706-5CrossRef

30.

Kunc, M.: Regular solutions of language inequalities and well quasi-orders. Theor. Comput. Sci. 348(2–3), 277–293 (2005)MathSciNetMATHCrossRef

31.

Kunc, M.: The power of commuting with finite sets of words. Theory Comput. Syst. 40(4), 521–551 (2007)MathSciNetMATHCrossRef

32.

Kunc, M., Okhotin, A.: Language equations. In: Pin, J.E. (ed.) Handbook of Automata Theory, vol. II, chap. 21. European Mathematical Society, Zürich (2020, To appear)

33.

Leupold, P.: Languages generated by iterated idempotency. Theor. Comput. Sci. 370(1–3), 170–185 (2007)MathSciNetMATHCrossRef

34.

Leupold, P.: On regularity-preservation by string-rewriting systems. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 345–356. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88282-4_32CrossRef

35.

McNaughton, R., Papert, S.: Counter-Free Automata. The M.I.T. Press, Cambridge (1971). With an appendix by William Henneman, M.I.T. ResearchMonograph, No. 65MATH

36.

Niwinśki, D., Rytter, W.: 200 Problems in Formal Languages and Automata Theory. University of Warsaw (2017)

37.

Otto, F.: On the connections between rewriting and formal language theory. In: Narendran, P., Rusinowitch, M. (eds.) RTA 1999. LNCS, vol. 1631, pp. 332–355. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48685-2_27MATHCrossRef

38.

Pin, J.-É.: Topologies for the free monoid. J. Algebra 137, 297–337 (1991)MathSciNetMATHCrossRef

39.

Pin, J.-É., Sakarovitch, J.: Some operations and transductions that preserve rationality. In: Cremers, A.B., Kriegel, H.-P. (eds.) GI-TCS 1983. LNCS, vol. 145, pp. 277–288. Springer, Heidelberg (1982). https://doi.org/10.1007/BFb0036488CrossRef

40.

Pin, J.-É., Sakarovitch, J.: Une application de la représentation matricielle des transductions. Theor. Comput. Sci. 35, 271–293 (1985)MATHCrossRef

41.

Pin, J.-É., Silva, P.V.: A topological approach to transductions. Theor. Comput. Sci. 340, 443–456 (2005)MathSciNetMATHCrossRef

42.

Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141, 1–35 (1969) MathSciNetMATH

43.

Restivo, A.: Codes and aperiodic languages. In: Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen (Bonn, 1973), LNCS, vol. 2, pp. 175–181. Springer, Berlin (1973)

44.

Restivo, A., Reutenauer, C.: On cancellation properties of languages which are supports of rational power series. J. Comput. Syst. Sci. 29(2), 153–159 (1984)MathSciNetMATHCrossRef

45.

Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009). Translated from the 2003 French original by Reuben ThomasMATHCrossRef

46.

Schützenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8, 190–194 (1965)MathSciNetMATHCrossRef

47.

Seiferas, J.I., McNaughton, R.: Regularity-preserving relations. Theor. Comput. Sci. 2(2), 147–154 (1976)MathSciNetMATHCrossRef

48.

Siefkes, D.: Decidable extensions of monadic second order successor arithmetic. In: Automatentheorie und formale Sprachen (Tagung, Math. Forschungsinst., Oberwolfach, 1969), pp. 441–472. Bibliographisches Inst., Mannheim (1970)

49.

Sipser, M.: Introduction to the Theory of Computation. 3rd edn. Cengage Learning (2012)

50.

Stanat, D.F., Weiss, S.F.: A pumping theorem for regular languages. SIGACT News 14(1), 36–37 (1982)MATHCrossRef

51.

Stearns, R.E., Hartmanis, J.: Regularity preserving modifications of regular expressions. Inf. Control 6, 55–69 (1963)MathSciNetMATHCrossRef

52.

Straubing, H.: Relational morphisms and operations on recognizable sets. RAIRO Inf. Theor. 15, 149–159 (1981)MathSciNetMATHCrossRef

53.

Trakhtenbrot, B.A.: Barzdin\(^{\prime }\), Y.M.: Finite Automata, Behavior and Synthesis. North-Holland Publishing Co., Amsterdam (1973). Translated from the Russian by D. Louvish, English translation edited by E. Shamir and L. H. Landweber, Fundamental Studies in Computer Science, vol. 1

54.

Varricchio, S.: A pumping condition for regular sets. SIAM J. Comput. 26(3), 764–771 (1997)MathSciNetMATHCrossRef

55.

Zhang, G.Q.: Automata, boolean matrices, and ultimate periodicity. Inform. Comput. 152(1), 138–154 (1999)MathSciNetMATHCrossRef

Titel: How to Prove that a Language Is Regular or Star-Free?
verfasst von: Jean-Éric Pin
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner