Syntactic structures of regular languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F19%3A00108218" target="_blank" >RIV/00216224:14310/19:00108218 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2019.10.020" target="_blank" >https://doi.org/10.1016/j.tcs.2019.10.020</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2019.10.020" target="_blank" >10.1016/j.tcs.2019.10.020</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Syntactic structures of regular languages

Popis výsledku v původním jazyce

Given a regular language, its canonical lattice automaton is defined - this is a modification of the notions of the minimal automaton and the canonical meet automaton of the language. Secondly, the concept of the syntactic lattice algebra is introduced as an analogy of the syntactic monoid and of the syntactic semiring. The above three syntactic structures are constructed as certain transformation algebras of the corresponding automata. This leads to a unified approach to the study of syntactic structures of regular languages. The basic properties of the new notions are stated, showing, among others, the minimality of the canonical lattice automaton and the minimality of the syntactic lattice algebra. Using the syntactic lattice algebra, a new characterization of the membership problem for reversible languages is given.

Název v anglickém jazyce

Syntactic structures of regular languages

Popis výsledku anglicky

Given a regular language, its canonical lattice automaton is defined - this is a modification of the notions of the minimal automaton and the canonical meet automaton of the language. Secondly, the concept of the syntactic lattice algebra is introduced as an analogy of the syntactic monoid and of the syntactic semiring. The above three syntactic structures are constructed as certain transformation algebras of the corresponding automata. This leads to a unified approach to the study of syntactic structures of regular languages. The basic properties of the new notions are stated, showing, among others, the minimality of the canonical lattice automaton and the minimality of the syntactic lattice algebra. Using the syntactic lattice algebra, a new characterization of the membership problem for reversible languages is given.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

800

Číslo periodika v rámci svazku

DEC 31 2019

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

17

Strana od-do

125-141

Kód UT WoS článku

000500371400010

EID výsledku v databázi Scopus

2-s2.0-85074470052