Počet záznamů: 1
Partially ordered automata and piecewise testability
- 1.
SYSNO ASEP 0542403 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Partially ordered automata and piecewise testability Tvůrce(i) Masopust, Tomáš (MU-W) RID, ORCID, SAI
Krötzsch, M. (DE)Číslo článku 14 Zdroj.dok. Logical Methods in Computer Science. - : Logical Methods in Computer Science - ISSN 1860-5974
Roč. 17, č. 2 (2021)Poč.str. 36 s. Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova automata ; nondeterminism ; complexity Vědní obor RIV BA - Obecná matematika Obor OECD Automation and control systems CEP GC19-06175J GA ČR - Grantová agentura ČR Způsob publikování Open access Institucionální podpora MU-W - RVO:67985840 UT WOS 000658731000014 EID SCOPUS 85108388804 DOI 10.23638/LMCS-17(2:14)2021 Anotace Partially ordered automata are automata where the transition relation induces a partial order on states. The expressive power of partially ordered automata is closely related to the expressivity of fragments of first-order logic on finite words or, equivalently, to the language classes of the levels of the Straubing-Thérien hierarchy. Several fragments (levels) have been intensively investigated under various names. For instance, the fragment of first-order formulae with a single existential block of quantifiers in prenex normal form is known as piecewise testable languages or J-trivial languages. These languages are characterized by confluent partially ordered DFAs or by complete, confluent, and self-loop-deterministic partially ordered NFAs (ptNFAs for short). In this paper, we study the complexity of basic questions for several types of partially ordered automata on finite words, namely, the questions of inclusion, equivalence, and (k-)piecewise testability. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2022 Elektronická adresa https://dx.doi.org/10.23638/LMCS-17(2:14)2021
Počet záznamů: 1