Partially ordered automata and piecewise testability
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F21%3A00542403" target="_blank" >RIV/67985840:_____/21:00542403 - isvavai.cz</a>
Alternative codes found
RIV/61989592:15310/21:73607926
Result on the web
<a href="https://dx.doi.org/10.23638/LMCS-17(2:14)2021" target="_blank" >https://dx.doi.org/10.23638/LMCS-17(2:14)2021</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.23638/LMCS-17(2:14)2021" target="_blank" >10.23638/LMCS-17(2:14)2021</a>
Alternative languages
Result language
angličtina
Original language name
Partially ordered automata and piecewise testability
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
20205 - Automation and control systems
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Logical Methods in Computer Science
ISSN
1860-5974
e-ISSN
1860-5974
Volume of the periodical
17
Issue of the periodical within the volume
2
Country of publishing house
DE - GERMANY
Number of pages
36
Pages from-to
14
UT code for WoS article
000658731000014
EID of the result in the Scopus database
2-s2.0-85108388804