D 2013

Alternative Automata Characterization of Piecewise Testable Languages

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

Základní údaje

Originální název

Alternative Automata Characterization of Piecewise Testable Languages

Autoři

KLÍMA, Ondřej (203 Česká republika, garant, domácí) a Libor POLÁK (203 Česká republika, domácí)

Vydání

Berlin Heidelberg, Developments in Language Theory, od s. 289-300, 12 s. 2013

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í

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14310/13:00066861

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-642-38770-8

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-38771-5_26

Klíčová slova anglicky

piecewise testable languages; acyclic automata; locally con- fluent automata

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 5. 3. 2014 14:46, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

V originále

We present a transparent condition on a minimal automaton which is equivalent to piecewise testability of the corresponding regular language. The condition simplifies the original Simon’s condition on the minimal automaton in a different way than conditions of Stern and Trahtman. Secondly, we prove that every piecewise testable language L is k-piecewise testable for k equal to the depth of the minimal DFA of L. This result improves all previously known estimates of such k.

Návaznosti

GBP202/12/G061, projekt VaV
Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky
Zobrazeno: 14. 11. 2024 16:58