RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor
Subscription
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Uspekhi Mat. Nauk, 1961, Volume 16, Issue 5(101), Pages 3–62 (Mi umn6668)  

This article is cited in 84 scientific papers (total in 84 papers)

The abstract theory of automata

V. M. Glushkov


Full text: PDF file (8794 kB)

English version:
Russian Mathematical Surveys, 1961, 16:5, 1–53

Bibliographic databases:

MSC: 68Q70, 20M35, 68Q65
Received: 21.04.1961

Citation: V. M. Glushkov, “The abstract theory of automata”, Uspekhi Mat. Nauk, 16:5(101) (1961), 3–62; Russian Math. Surveys, 16:5 (1961), 1–53

Citation in format AMSBIB
\Bibitem{Glu61}
\by V.~M.~Glushkov
\paper The abstract theory of automata
\jour Uspekhi Mat. Nauk
\yr 1961
\vol 16
\issue 5(101)
\pages 3--62
\mathnet{http://mi.mathnet.ru/umn6668}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=138529}
\zmath{https://zbmath.org/?q=an:0104.35404}
\transl
\jour Russian Math. Surveys
\yr 1961
\vol 16
\issue 5
\pages 1--53
\crossref{https://doi.org/10.1070/RM1961v016n05ABEH004112}


Linking options:
  • http://mi.mathnet.ru/eng/umn6668
  • http://mi.mathnet.ru/eng/umn/v16/i5/p3

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Erratum
    • A correction
      V. M. Glushkov
      Uspekhi Mat. Nauk, 1962, 17:2(104), 270


    This publication is cited in the following articles:
    1. Robert Rosen, “Abstract biological systems as sequential machines”, Bulletin of Mathematical Biophysics, 26:2 (1964), 103  crossref  mathscinet
    2. D. L. Kreider, R. W. Ritchie, “PREDICTABLY COMPUTABLE FUNCTIONALS AND DEFINITION BY RECURSION”, Z Math Logik Grundlagen Math, 10:5 (1964), 65  crossref  mathscinet  zmath
    3. Walter R. Stahl, “Algorithmically unsolvable problems for a cell automaton”, Journal of Theoretical Biology, 8:3 (1965), 371  crossref
    4. Robert Rosen, “Abstract biological systems as sequential machines: III. Some algebraic aspects”, Bulletin of Mathematical Biophysics, 28:2 (1966), 141  crossref  mathscinet
    5. V. N. Lifshits, L. E. Sadovskii, “Algebraic models of computing machines”, Russian Math. Surveys, 27:3 (1972), 87–135  mathnet  crossref  mathscinet  zmath
    6. M. W. Warner, “Representations of (M, R)-systems by categories of automata”, Bull Math Biol, 44:5 (1982), 661  crossref  mathscinet  zmath  isi
    7. Anne Brüggemann-Klein, “Regular expressions into finite automata”, Theoretical Computer Science, 120:2 (1993), 197  crossref
    8. Jean Berstel, Jean-Eric Pin, “Local languages and the Berry-Sethi algorithm”, Theoretical Computer Science, 155:2 (1996), 439  crossref
    9. Valentin Antimirov, “Partial derivatives of regular expressions and finite automaton constructions”, Theoretical Computer Science, 155:2 (1996), 291  crossref
    10. A. Brüggemann-Klein, D. Wood, “The validation of SGML content models”, Mathematical and Computer Modelling, 25:4 (1997), 73  crossref
    11. Anne Brüggemann-Klein, Derick Wood, “One-Unambiguous Regular Languages”, Information and Computation, 142:2 (1998), 182  crossref
    12. Anne Brüggemann-Klein, Derick Wood, “One-Unambiguous Regular Languages”, Information and Computation, 140:2 (1998), 229  crossref
    13. J.-M. Champarnaud, J.-L. Ponty, D. Ziadi, “From regular expressions to finite automata∗”, International Journal of Computer Mathematics, 72:4 (1999), 415  crossref
    14. Djelloul Ziadi, Jean-Marc Champarnaud, “An optimal parallel algorithm to convert a regular expression into its Glushkov automaton”, Theoretical Computer Science, 215:1-2 (1999), 69  crossref
    15. R. I. Grigorchuk, V. V. Nekrashevych, “The group of asynchronous automata and rational homeomorphisms of the Cantor set”, Math. Notes, 67:5 (2000), 577–581  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    16. Proc. Steklov Inst. Math., 231 (2000), 1–41  mathnet  mathscinet  zmath
    17. R. I. Grigorchuk, V. V. Nekrashevych, V. I. Sushchanskii, “Automata, Dynamical Systems, and Groups”, Proc. Steklov Inst. Math., 231 (2000), 128–203  mathnet  mathscinet  zmath
    18. Pascal Caron, Djelloul Ziadi, “Characterization of Glushkov automata”, Theoretical Computer Science, 233:1-2 (2000), 75  crossref
    19. J.-L. Ponty, “An efficient null-free procedure for deciding regular language membership”, Theoretical Computer Science, 231:1 (2000), 89  crossref
    20. Juraj Hromkovič, Sebastian Seibert, Thomas Wilke, “Translating Regular Expressions into Small ε-Free Nondeterministic Finite Automata”, Journal of Computer and System Sciences, 62:4 (2001), 565  crossref
    21. J.-M. Champarnaud, “Subset construction complexity for homogeneous automata, position automata and ZPC-structures”, Theoretical Computer Science, 267:1-2 (2001), 17  crossref
    22. J.-M. CHAMPARNAUD, D. ZIADI, “FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS”, Int. J. Algebra Comput, 11:06 (2001), 707  crossref
    23. I. I. Reznikov, V. I. Sushchanskii, “Two-State Mealy Automata of Intermediate Growth over a Two-Letter Alphabet”, Math. Notes, 72:1 (2002), 90–104  mathnet  crossref  crossref  mathscinet  zmath  isi
    24. J.-M. Champarnaud, D. Ziadi, “Canonical derivatives, partial derivatives and finite automaton constructions”, Theoretical Computer Science, 289:1 (2002), 137  crossref
    25. JEAN-MARC CHAMPARNAUD, “EVALUATION OF THREE IMPLICIT STRUCTURES TO IMPLEMENT NONDETERMINISTIC AUTOMATA FROM REGULAR EXPRESSIONS”, Int. J. Found. Comput. Sci, 13:01 (2002), 99  crossref
    26. E. Mochko, V. V. Nekrashevych, V. I. Sushchanskii, “Dynamics of Triangular Transformations of Sequences over Finite Alphabets”, Math. Notes, 73:3 (2003), 436–439  mathnet  crossref  crossref  mathscinet  zmath  isi
    27. A. Ádám, M. Laczkovich, “On cardinality questions concerning automaton mappings”, SScMath, 40:1 (2003), 71  crossref
    28. Pascal Caron, Marianne Flouret, “Glushkov Construction For Series: The Non Commutative Case”, International Journal of Computer Mathematics, 80:4 (2003), 457  crossref
    29. Lucian Ilie, Sheng Yu, “Follow automata”, Information and Computation, 186:1 (2003), 140  crossref
    30. Lucian Ilie, Sheng Yu, “Reducing NFAs by invariant equivalences”, Theoretical Computer Science, 306:1-3 (2003), 373  crossref
    31. Yuri Lifshits, “A lower bound on the size of ε-free NFA corresponding to a regular expression”, Information Processing Letters, 85:6 (2003), 293  crossref
    32. Gonzalo Navarro, “Regular expression searching on compressed text”, Journal of Discrete Algorithms, 1:5-6 (2003), 423  crossref
    33. Guangming Xing, “Minimized Thompson NFA”, International Journal of Computer Mathematics, 81:9 (2004), 1097  crossref
    34. Sylvain Lombardy, Jacques Sakarovitch, “How expressions can code for automata”, RAIRO-Theor. Inf. Appl, 39:1 (2005), 217  crossref
    35. Sylvain Lombardy, Jacques Sakarovitch, “Derivatives of rational expressions with multiplicity”, Theoretical Computer Science, 332:1-3 (2005), 141  crossref
    36. J.-M. CHAMPARNAUD, F. COULON, T. PARANTHOËN, “BRUTE FORCE DETERMINIZATION OF NFAs BY MEANS OF STATE COVERS”, Int. J. Found. Comput. Sci, 16:03 (2005), 441  crossref
    37. J.-M. CHAMPARNAUD, F. NICART, D. ZIADI, “FROM THE STRUCTURE OF A REGULAR EXPRESSION TO ITS FOLLOW AUTOMATON”, Int. J. Algebra Comput, 16:01 (2006), 17  crossref
    38. Salvatore Torre, Margherita Napoli, Mimmo Parente, “The word problem for visibly pushdown languages described by grammars”, Form Method Syst Des, 31:3 (2007), 265  crossref  zmath  isi
    39. Faissal Ouardi, Djelloul Ziadi, “Efficient weighted expressions conversion”, RAIRO-Theor. Inf. Appl, 42:2 (2007), 285  crossref
    40. Thomas Schwentick, “Automata for XML—A survey”, Journal of Computer and System Sciences, 73:3 (2007), 289  crossref
    41. Pekka Kilpeläinen, Rauno Tuhkanen, “One-unambiguity of regular expressions with numeric occurrence indicators”, Information and Computation, 205:6 (2007), 890  crossref
    42. Y. André, A.C. Caron, D. Debarbieux, Y. Roos, S. Tison, “Path constraints in semistructured data”, Theoretical Computer Science, 385:1-3 (2007), 11  crossref
    43. Juraj Hromkovič, Georg Schnitger, “Comparing the size of NFAs with and without -transitions”, Theoretical Computer Science, 380:1-2 (2007), 100  crossref
    44. Yo-Sub Han, Derick Wood, “Obtaining shorter regular expressions from finite-state automata”, Theoretical Computer Science, 370:1-3 (2007), 110  crossref
    45. J.-M. CHAMPARNAUD, F. OUARDI, D. ZIADI, “NORMALIZED EXPRESSIONS AND FINITE AUTOMATA”, Int. J. Algebra Comput, 17:01 (2007), 141  crossref
    46. Vassilios Karakoidas, Diomidis Spinellis, “FIRE/J—optimizing regular expression searches with generative programming”, Softw Pract Exper, 38:6 (2008), 557  crossref  isi
    47. Yo-Sub Han, Derick Wood, “Generalizations of 1-deterministic regular languages”, Information and Computation, 206:9-10 (2008), 1117  crossref
    48. S. V. Aleshin, “Automata in algebra”, J. Math. Sci., 168:1 (2010), 14–20  mathnet  crossref  mathscinet  elib
    49. MARCO ALMEIDA, NELMA MOREIRA, ROGÉRIO REIS, “ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED”, Int. J. Found. Comput. Sci, 20:04 (2009), 669  crossref
    50. V. B. Kudryavtsev, I. S. Grunskii, V. A. Kozlovskii, “Analysis and synthesis of abstract automata”, J. Math. Sci., 169:4 (2010), 481–532  mathnet  crossref  mathscinet  elib  elib
    51. V. B. Kudryavtsev, I. S. Grunskii, V. A. Kozlovskii, “Analysis of behaviour of automata”, Discrete Math. Appl., 19:1 (2009), 1–35  mathnet  crossref  crossref  mathscinet  elib
    52. V. B. Kudryavtsev, I. S. Grunskii, V. A. Kozlovskii, “Reconstruction of automata by fragments of behaviour”, Discrete Math. Appl., 19:2 (2009), 113–154  mathnet  crossref  crossref  mathscinet  elib
    53. Davide Pasetto, Fabrizio Petrini, Virat Agarwal, “DotStar: breaking the scalability and performance barriers in parsing regular expressions”, Comp Sci Res Dev, 2010  crossref
    54. Sylvain Lombardy, Jacques Sakarovitch, “Corrigendum to our paper: How Expressions Can Code for Automata”, Theoret Informatics Appl, 2010  crossref
    55. “Letters to the Editor”, Comput, 43:3 (2010), 6  crossref
    56. Olivier Kaczor, Yann-Gaël Guéhéneuc, Sylvie Hamel, “Identification of design motifs with pattern matching algorithms”, Information and Software Technology, 52:2 (2010), 152  crossref
    57. Kefu Xu, Jianlong Tan, Li Guo, Binxing Fang, “Traffic-Aware Frequent Elements Matching Algorithms for Deep Packet Inspection”, Jnw, 6:5 (2011)  crossref
    58. Pedro García, Damián López, José Ruiz, Gloria I. Álvarez, “From regular expressions to smaller NFAs”, Theoretical Computer Science, 2011  crossref
    59. Dietrich Kuske, Ingmar Meinecke, “Construction of tree automata from regular expressions”, RAIRO-Theor. Inf. Appl, 2011  crossref
    60. Pekka Kilpeläinen, “Checking determinism of XML Schema content models in optimal time”, Information Systems, 36:3 (2011), 596  crossref
    61. Dag Hovland, “The inclusion problem for regular expressions”, Journal of Computer and System Sciences, 2011  crossref
    62. Savchuk D., Vorobets Ya., “Automata generating free products of groups of order 2”, J Algebra, 336:1 (2011), 53–66  crossref  isi
    63. MARKUS HOLZER, MARTIN KUTRIB, “THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS”, Int. J. Found. Comput. Sci, 22:07 (2011), 1533  crossref
    64. Aleksandar Stamenković, Miroslav Ćirić, “Construction of fuzzy automata from fuzzy regular expressions”, Fuzzy Sets and Systems, 2012  crossref
    65. Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot, “Multi-tilde-bar expressions and their automata”, Acta Informatica, 2012  crossref
    66. SABINE BRODA, ANTÓNIO MACHIAVELO, NELMA MOREIRA, ROGÉRIO REIS, “ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA”, Int. J. Found. Comput. Sci, 23:05 (2012), 969  crossref
    67. G.I.. Szabó, András Benczúr, “Functional dependencies on extended relations defined by regular languages”, Ann Math Artif Intell, 2013  crossref
    68. Paul Gastin, Benjamin Monmege, “Adding Pebbles to Weighted Automata Easy Specification & Efficient Evaluation”, Theoretical Computer Science, 2014  crossref
    69. Ludovic Mignot, Nadia Ouali Sebti, Djelloul Ziadi, “K-Position, Follow, Equation and K-C-Continuation Tree Automata Constructions”, Electron. Proc. Theor. Comput. Sci, 151 (2014), 327  crossref
    70. Hermann Gruber, Markus Holzer, “From Finite Automata to Regular Expressions and Back—A Summary on Descriptional Complexity”, Electron. Proc. Theor. Comput. Sci, 151 (2014), 25  crossref
    71. José R. González de Mendívil, José R. Garitagoitia, “A comment on “Construction of fuzzy automata from fuzzy regular expressions””, Fuzzy Sets and Systems, 2014  crossref
    72. Yong-yi YAN, Zeng-qiang CHEN, Zhong-xin LIU, “Verification analysis of self-verifying automata via semi-tensor product of matrices”, The Journal of China Universities of Posts and Telecommunications, 21:4 (2014), 96  crossref
    73. Ping Lu, Joachim Bremer, Haiming Chen, “Deciding Determinism of Regular Languages”, Theory Comput Syst, 2014  crossref
    74. Maohua Jing, Yixian Yang, Ning Lu, Wenbo Shi, Changyong Yu, “Postfix automata”, Theoretical Computer Science, 2014  crossref
    75. Yannick Nke, Jan Lunze, “Control Design for Nondeterministic Input/Output Automata”, European Journal of Control, 2014  crossref
    76. MARKUS HOLZER, SEBASTIAN JAKOBI, “NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY”, Int. J. Found. Comput. Sci, 25:07 (2014), 837  crossref
    77. Sutner K., “Iteration of Invertible Transductions”, Int. J. Found. Comput. Sci., 25:7, SI (2014), 857–875  crossref  isi
    78. V. P. Tsvetov, “Ob odnom nadklasse A-grammatik”, Vestn. SamGU. Estestvennonauchn. ser., 2014, no. 10(121), 102–108  mathnet
    79. Shoham Ben-David, Fady Copty, Dana Fisman, Sitvanit Ruah, “Vacuity in practice: temporal antecedent failure”, Form Methods Syst Des, 46:1 (2015), 81  crossref
    80. Faissal Ouardi, Jean-Marc Champarnaud, Djelloul Ziadi, “Extended to multi-tilde-bar regular expressions and efficient finite automata constructions”, Journal of Discrete Algorithms, 2015  crossref
    81. Xiaoman Chen, Jiawen Zhang, “Large scale properties for bounded automata groups”, Journal of Functional Analysis, 2015  crossref
    82. Yeim-Kuan Chang, Yuen-Shuo Li, Yu-To Chen, “A Memory Efficient DFA Using Compression and Pattern Segmentation”, Procedia Computer Science, 56 (2015), 292  crossref
    83. Paul Brunet, Damien Pous, “Algorithms for Kleene algebra with converse”, Journal of Logical and Algebraic Methods in Programming, 2015  crossref
    84. A. A. Demidov, “O popolnenii gruppoida do programmnoi algebry”, Programmnye sistemy: teoriya i prilozheniya, 6:3 (2015), 45–52  mathnet
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:3119
    Full text:1089
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018