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 -