On Varieties of Ordered Automata

D 2019

On Varieties of Ordered Automata

KLÍMA, Ondřej a Libor POLÁK

Základní údaje

Originální název

On Varieties of Ordered Automata

Autoři

KLÍMA, Ondřej a Libor POLÁK

Vydání

Germany, Language and Automata Theory and Applications, od s. 108-120, 13 s. 2019

Nakladatel

Springer Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14310/19:00108264

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-030-13434-1

ISSN

DOI

https://doi.org/10.1007/978-3-030-13435-8_8

EID Scopus

2-s2.0-85064040868

Klíčová slova anglicky

Algebraic language theory; Ordered automata

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 15. 4. 2020 13:42, Mgr. Marie Novosadová Šípková, DiS.

Anotace

V originále

The Eilenberg correspondence relates varieties of regular languages with pseudovarieties of finite monoids. Various modifications of this correspondence have been found with more general classes of regular languages on one hand and classes of more complex algebraic structures on the other hand. It is also possible to consider classes of automata instead of algebraic structures as a natural counterpart of classes of languages. Here we deal with the correspondence relating positive C -varieties of languages to positive C -varieties of ordered automata and we demonstrate various specific instances of this correspondence. These bring certain well-known results from a new perspective and also some new observations. Moreover, complexity aspects of the membership problem are discussed both in the particular examples and in a general setting.

Návaznosti

GA15-02862S, projekt VaV

Název: Aplikace algebry a kombinatoriky v teorii formálních jazyků

Investor: Grantová agentura ČR, Aplikace algebry a kombinatoriky v teorii formálních jazyků

Citovat

KLÍMA, Ondřej a Libor POLÁK. On Varieties of Ordered Automata. Online. In Carlos Martín-Vide; Alexander Okhotin; Dana Shapira. Language and Automata Theory and Applications. Germany: Springer Verlag, 2019, s. 108-120. ISBN 978-3-030-13434-1. Dostupné z: https://doi.org/10.1007/978-3-030-13435-8_8.

@inproceedings{1645723,
   author = {Klíma, Ondřej and Polák, Libor},
   address = {Germany},
   booktitle = {Language and Automata Theory and Applications},
   doi = {https://doi.org/10.1007/978-3-030-13435-8_8},
   editor = {Carlos Martín-Vide; Alexander Okhotin; Dana Shapira},
   keywords = {Algebraic language theory; Ordered automata},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Germany},
   isbn = {978-3-030-13434-1},
   pages = {108-120},
   publisher = {Springer Verlag},
   title = {On Varieties of Ordered Automata},
   url = {https://rd.springer.com/chapter/10.1007%2F978-3-030-13435-8_8},
   year = {2019}
}

TY  - CONF
ID  - 1645723
AU  - Klíma, Ondřej - Polák, Libor
PY  - 2019
TI  - On Varieties of Ordered Automata
PB  - Springer Verlag
CY  - Germany
SN  - 9783030134341
KW  - Algebraic language theory
KW  - Ordered automata
UR  - https://rd.springer.com/chapter/10.1007%2F978-3-030-13435-8_8
L2  - https://rd.springer.com/chapter/10.1007%2F978-3-030-13435-8_8
N2  - The Eilenberg correspondence relates varieties of regular languages with pseudovarieties of finite monoids. Various modifications of this correspondence have been found with more general classes of regular languages on one hand and classes of more complex algebraic structures on the other hand. It is also possible to consider classes of automata instead of algebraic structures as a natural counterpart of classes of languages. Here we deal with the correspondence relating positive C -varieties of languages to positive C -varieties of ordered automata and we demonstrate various specific instances of this correspondence. These bring certain well-known results from a new perspective and also some new observations. Moreover, complexity aspects of the membership problem are discussed both in the particular examples and in a general setting.
ER  -

KLÍMA, Ondřej a Libor POLÁK. On Varieties of Ordered Automata. Online. In Carlos Martín-Vide; Alexander Okhotin; Dana Shapira. \textit{Language and Automata Theory and Applications}. Germany: Springer Verlag, 2019, s.~108-120. ISBN~978-3-030-13434-1. Dostupné z: https://doi.org/10.1007/978-3-030-13435-8\_{}8.

Přehled o publikaci