10.23638/LMCS-17(2:14)2021
Masopust, Tomáš
Tomáš
Masopust
Krötzsch, Markus
Markus
Krötzsch
Partially Ordered Automata and Piecewise Testability
episciences.org
2021
Computer Science - Logic in Computer Science
Computer Science - Formal Languages and Automata Theory
contact@episciences.org
episciences.org
2019-11-11T10:54:03+01:00
2021-05-11T14:57:11+02:00
2021-05-11
eng
Journal article
https://lmcs.episciences.org/5900
arXiv:1907.13115
1860-5974
PDF
1
Logical Methods in Computer Science ; Volume 17, Issue 2 ; 1860-5974
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\'erien 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. The lower-bound
complexity boils down to the complexity of universality. The universality
problem asks whether a system recognizes all words over its alphabet. For
ptNFAs, the complexity of universality decreases if the alphabet is fixed, but
it is open if the alphabet may grow with the number of states. We show that
deciding universality for general ptNFAs is as hard as for general NFAs. Our
proof is a novel and nontrivial extension of our recent construction for
self-loop-deterministic partially ordered NFAs, a model strictly more
expressive than ptNFAs. We provide a comprehensive picture of the complexities
of the problems of inclusion, equivalence, and ($k$-)piecewise testability for
the considered types of automata.
Comment: arXiv admin note: text overlap with arXiv:1704.07860