Standard

Some reducibilities on regular sets. / Selivanov, Victor L.

Some reducibilities on regular sets. Vol. 3526 2005. p. 430-439 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

Harvard

Selivanov, VL 2005, Some reducibilities on regular sets. in Some reducibilities on regular sets. vol. 3526, Lecture Notes in Computer Science, pp. 430-439. https://doi.org/10.1007/11494645_53

APA

Selivanov, V. L. (2005). Some reducibilities on regular sets. In Some reducibilities on regular sets (Vol. 3526, pp. 430-439). (Lecture Notes in Computer Science). https://doi.org/10.1007/11494645_53

Vancouver

Selivanov VL. Some reducibilities on regular sets. In Some reducibilities on regular sets. Vol. 3526. 2005. p. 430-439. (Lecture Notes in Computer Science). https://doi.org/10.1007/11494645_53

Author

Selivanov, Victor L. / Some reducibilities on regular sets. Some reducibilities on regular sets. Vol. 3526 2005. pp. 430-439 (Lecture Notes in Computer Science).

BibTeX

@inbook{9447bdc8c21d48298795759d0585d381,
title = "Some reducibilities on regular sets",
abstract = "We discuss some known and introduce some new reducibilities on regular sets. We establish some facts on the corresponding degree structures and relate some reducibilities to natural hierarchies of regular sets. As an application, we characterize regular languages whose leaf-language classes (in the balanced model) are contained in the polynomial hierarchy. For any reducibility we try to give some motivation and interesting open questions, in a hope to convince the reader that study of these reducibilities is important for automata theory and computational complexity. {\textcopyright} Springer-Verlag Berlin Heidelberg 2005.",
author = "Selivanov, {Victor L.}",
year = "2005",
month = jan,
day = "1",
doi = "10.1007/11494645_53",
language = "English",
volume = "3526",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "430--439",
booktitle = "Some reducibilities on regular sets",

}

RIS

TY - CHAP

T1 - Some reducibilities on regular sets

AU - Selivanov, Victor L.

PY - 2005/1/1

Y1 - 2005/1/1

N2 - We discuss some known and introduce some new reducibilities on regular sets. We establish some facts on the corresponding degree structures and relate some reducibilities to natural hierarchies of regular sets. As an application, we characterize regular languages whose leaf-language classes (in the balanced model) are contained in the polynomial hierarchy. For any reducibility we try to give some motivation and interesting open questions, in a hope to convince the reader that study of these reducibilities is important for automata theory and computational complexity. © Springer-Verlag Berlin Heidelberg 2005.

AB - We discuss some known and introduce some new reducibilities on regular sets. We establish some facts on the corresponding degree structures and relate some reducibilities to natural hierarchies of regular sets. As an application, we characterize regular languages whose leaf-language classes (in the balanced model) are contained in the polynomial hierarchy. For any reducibility we try to give some motivation and interesting open questions, in a hope to convince the reader that study of these reducibilities is important for automata theory and computational complexity. © Springer-Verlag Berlin Heidelberg 2005.

UR - http://www.scopus.com/inward/record.url?scp=26444466110&partnerID=8YFLogxK

U2 - 10.1007/11494645_53

DO - 10.1007/11494645_53

M3 - Chapter

AN - SCOPUS:26444466110

VL - 3526

T3 - Lecture Notes in Computer Science

SP - 430

EP - 439

BT - Some reducibilities on regular sets

ER -

ID: 127140043