Skip to main content
Top

2020 | OriginalPaper | Chapter

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

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Footnotes
1
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.
 
Literature
1.
go back to reference 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 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
2.
go back to reference Berstel, J.: Transductions and Context-Free Languages. Teubner (1979) Berstel, J.: Transductions and Context-Free Languages. Teubner (1979)
3.
go back to reference Berstel, J., Boasson, L., Carton, O., Petazzoni, B., Pin, J.-É.: Operations preserving recognizable languages. Theor. Comput. Sci. 354, 405–420 (2006)MATHCrossRef Berstel, J., Boasson, L., Carton, O., Petazzoni, B., Pin, J.-É.: Operations preserving recognizable languages. Theor. Comput. Sci. 354, 405–420 (2006)MATHCrossRef
5.
go back to reference 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 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
6.
go back to reference Bucher, W., Ehrenfeucht, A., Haussler, D.: On total regulators generated by derivation relations. Theor. Comput. Sci. 40(2–3), 131–148 (1985)MathSciNetMATHCrossRef Bucher, W., Ehrenfeucht, A., Haussler, D.: On total regulators generated by derivation relations. Theor. Comput. Sci. 40(2–3), 131–148 (1985)MathSciNetMATHCrossRef
8.
go back to reference Büchi, J.R.: Regular canonical systems. Arch. Math. Logik Grundlagenforsch. 6, 91–111 (1964) (1964) Büchi, J.R.: Regular canonical systems. Arch. Math. Logik Grundlagenforsch. 6, 91–111 (1964) (1964)
9.
go back to reference Carton, O.: Langages formels, calculabilité et complexité. Vuibert (2008) Carton, O.: Langages formels, calculabilité et complexité. Vuibert (2008)
10.
11.
go back to reference Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971)MATH Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971)MATH
14.
16.
go back to reference Ehrenfeucht, A., Rozenberg, G.: On regularity of languages generated by copying systems. Discrete Appl. Math. 8(3), 313–317 (1984)MathSciNetMATHCrossRef Ehrenfeucht, A., Rozenberg, G.: On regularity of languages generated by copying systems. Discrete Appl. Math. 8(3), 313–317 (1984)MathSciNetMATHCrossRef
20.
21.
22.
23.
go back to reference 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 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
25.
go back to reference Kamp, J.: Tense Logic and the Theory of Linear Order. Ph.D. thesis, University of California, Los Angeles (1968) Kamp, J.: Tense Logic and the Theory of Linear Order. Ph.D. thesis, University of California, Los Angeles (1968)
26.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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 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
30.
32.
go back to reference 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) 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)
35.
go back to reference 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 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.
go back to reference Niwinśki, D., Rytter, W.: 200 Problems in Formal Languages and Automata Theory. University of Warsaw (2017) Niwinśki, D., Rytter, W.: 200 Problems in Formal Languages and Automata Theory. University of Warsaw (2017)
40.
go back to reference Pin, J.-É., Sakarovitch, J.: Une application de la représentation matricielle des transductions. Theor. Comput. Sci. 35, 271–293 (1985)MATHCrossRef Pin, J.-É., Sakarovitch, J.: Une application de la représentation matricielle des transductions. Theor. Comput. Sci. 35, 271–293 (1985)MATHCrossRef
42.
go back to reference Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141, 1–35 (1969) MathSciNetMATH Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141, 1–35 (1969) MathSciNetMATH
43.
go back to reference 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) 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.
go back to reference 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 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.
go back to reference Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009). Translated from the 2003 French original by Reuben ThomasMATHCrossRef Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009). Translated from the 2003 French original by Reuben ThomasMATHCrossRef
48.
go back to reference 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) 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.
go back to reference Sipser, M.: Introduction to the Theory of Computation. 3rd edn. Cengage Learning (2012) Sipser, M.: Introduction to the Theory of Computation. 3rd edn. Cengage Learning (2012)
50.
go back to reference Stanat, D.F., Weiss, S.F.: A pumping theorem for regular languages. SIGACT News 14(1), 36–37 (1982)MATHCrossRef Stanat, D.F., Weiss, S.F.: A pumping theorem for regular languages. SIGACT News 14(1), 36–37 (1982)MATHCrossRef
51.
53.
go back to reference 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 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
Metadata
Title
How to Prove that a Language Is Regular or Star-Free?
Author
Jean-Éric Pin
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-40608-0_5

Premium Partner