Partially ordered automata and piecewise testability

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/61989592:15310/21:73607926

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Partially ordered automata and piecewise testability

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Partially ordered automata and piecewise testability

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20205 - Automation and control systems

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

1860-5974

Svazek periodika

17

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

36

Strana od-do

14

Kód UT WoS článku

000658731000014

EID výsledku v databázi Scopus

2-s2.0-85108388804