Number of the records: 1
Partially ordered automata and piecewise testability
- 1.
SYSNO ASEP 0542403 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Partially ordered automata and piecewise testability Author(s) Masopust, Tomáš (MU-W) RID, ORCID, SAI
Krötzsch, M. (DE)Article number 14 Source Title Logical Methods in Computer Science. - : Logical Methods in Computer Science - ISSN 1860-5974
Roč. 17, č. 2 (2021)Number of pages 36 s. Language eng - English Country DE - Germany Keywords automata ; nondeterminism ; complexity Subject RIV BA - General Mathematics OECD category Automation and control systems R&D Projects GC19-06175J GA ČR - Czech Science Foundation (CSF) Method of publishing Open access Institutional support MU-W - RVO:67985840 UT WOS 000658731000014 EID SCOPUS 85108388804 DOI 10.23638/LMCS-17(2:14)2021 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2022 Electronic address https://dx.doi.org/10.23638/LMCS-17(2:14)2021
Number of the records: 1