Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






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


Zapiski Nauchnykh Seminarov LOMI, 1974, Volume 40, Pages 14–23 (Mi znsl2677)  

An upper estimate of the finite-state complexity for a class of generating schemes containing complements and intersections

Z. R. Dang, G. S. Tseitin
Abstract: Generating schemes (GS) are a method for generating regular sets of words that generalizes usual relular expressions on two lines: (1) the operations of set-theoretic complement and intersection are allowed, (2) oriented graphs with sets of words attached to their arcs are used in place of operations of union, concatenation and iteration of sets. The minimal number of states of a finite automaton that accepts the set represented by a GS is estimated in terms of the complexity of that GS. This function, as shown in [1], grows very rapidly for the class of all GS but is bounded by a $2^{2^n}$-like function for a class of GS specified in terms of admissible positions of intersections and complements.
In this paper the estimate is improved, viz., $2^{2^n}$ is replaced by $\psi(n)$, the number of monotonous boolean functions of $n$ variables. The proof is based on a special relationship involving sets of words and sets of vertices and arcs of the GS.
Bibliographic databases:
UDC: 51.01+518.5
Language: Russian
Citation: Z. R. Dang, G. S. Tseitin, “An upper estimate of the finite-state complexity for a class of generating schemes containing complements and intersections”, Studies in constructive mathematics and mathematical logic. Part VI, Zap. Nauchn. Sem. LOMI, 40, "Nauka", Leningrad. Otdel., Leningrad, 1974, 14–23
Citation in format AMSBIB
\Bibitem{DanTse74}
\by Z.~R.~Dang, G.~S.~Tseitin
\paper An upper estimate of the finite-state complexity for a~class of generating schemes containing complements and intersections
\inbook Studies in constructive mathematics and mathematical logic. Part~VI
\serial Zap. Nauchn. Sem. LOMI
\yr 1974
\vol 40
\pages 14--23
\publ "Nauka", Leningrad. Otdel.
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl2677}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=439600}
\zmath{https://zbmath.org/?q=an:0358.94065}
Linking options:
  • https://www.mathnet.ru/eng/znsl2677
  • https://www.mathnet.ru/eng/znsl/v40/p14
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:168
    Full-text PDF :52
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024