Počet záznamů: 1  

Partially ordered automata and piecewise testability

  1. 1.
    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.438, rok: 2020
    Způsob publikování: Open access

    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

    Název souboruStaženoVelikostKomentářVerzePřístup
    Masopust1.pdf4866.6 KBVydavatelský postprintpovolen
Počet záznamů: 1