|
Izv. Vyssh. Uchebn. Zaved. Mat., 2016, Number 7, Pages 55–65
(Mi ivm9134)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Automata transformations of prefix decidable and decidable by Buchi superwords
N. N. Korneeva Kazan (Volga Region) Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
Abstract:
We show that the set of prefix decidable superwords is closed under finite automata and asynchronous automata transformations. We prove that structures of degrees of finite automata and asynchronous automata transformations contain an atom which consists of prefix decidable superwords with undecidable monadic theory (or undecidable by Buchi). Also we prove that the structure of degrees of asynchronous automata transformations contains an atom which consists of superwords with decidable monadic theory (decidable by Buchi).
Keywords:
superword, prefix decidability, decidability by Buchi, monadic theory, automata transformation, degrees, atom.
Full text:
PDF file (216 kB)
References:
PDF file
HTML file
English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2016, 60:7, 47–55
Bibliographic databases:
UDC:
510.53 Received: 18.12.2014
Citation:
N. N. Korneeva, “Automata transformations of prefix decidable and decidable by Buchi superwords”, Izv. Vyssh. Uchebn. Zaved. Mat., 2016, no. 7, 55–65; Russian Math. (Iz. VUZ), 60:7 (2016), 47–55
Citation in format AMSBIB
\Bibitem{Kor16}
\by N.~N.~Korneeva
\paper Automata transformations of prefix decidable and decidable by Buchi superwords
\jour Izv. Vyssh. Uchebn. Zaved. Mat.
\yr 2016
\issue 7
\pages 55--65
\mathnet{http://mi.mathnet.ru/ivm9134}
\transl
\jour Russian Math. (Iz. VUZ)
\yr 2016
\vol 60
\issue 7
\pages 47--55
\crossref{https://doi.org/10.3103/S1066369X16070070}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000409301300007}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84975862651}
Linking options:
http://mi.mathnet.ru/eng/ivm9134 http://mi.mathnet.ru/eng/ivm/y2016/i7/p55
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:
-
N. N. Korneeva, “The structure of degrees of finite automaton transformations of prefix decidable superwords”, Russian Math. (Iz. VUZ), 60:9 (2016), 79–83
|
Number of views: |
This page: | 129 | Full text: | 20 | References: | 15 | First page: | 5 |
|