Partially ordered automata and piecewise testability

0542403 - MÚ 2022 RIV DE eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR(CZ) GC19-06175J
Institucionální podpora: RVO:67985840
Klíčová slova: automata * nondeterminism * complexity
Obor OECD: Automation and control systems
Impakt faktor: 0.591, rok: 2021
Způsob publikování: 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.
Trvalý link: http://hdl.handle.net/11104/0319817