Partially ordered automata and piecewise testability

0542403 - MÚ 2022 RIV DE eng J - Journal Article
Masopust, Tomáš - Krötzsch, M.
Partially ordered automata and piecewise testability.
Logical Methods in Computer Science. Roč. 17, č. 2 (2021), č. článku 14. ISSN 1860-5974. E-ISSN 1860-5974
R&D Projects: GA ČR(CZ) GC19-06175J
Institutional support: RVO:67985840
Keywords : automata * nondeterminism * complexity
OECD category: Automation and control systems
Impact factor: 0.591, year: 2021
Method of publishing: Open access
https://dx.doi.org/10.23638/LMCS-17(2:14)2021

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.
Permanent Link: http://hdl.handle.net/11104/0319817