Descriptional Complexity of Biautomata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F12%3A00057568" target="_blank" >RIV/00216224:14310/12:00057568 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-31623-4_15" target="_blank" >http://dx.doi.org/10.1007/978-3-642-31623-4_15</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-31623-4_15" target="_blank" >10.1007/978-3-642-31623-4_15</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Descriptional Complexity of Biautomata

Popis výsledku v původním jazyce

A biautomaton is a finite automaton which arbitrarily alternates between reading the input word from the left and from the right. Some compatibility assumptions in the formal definition of a biautomaton ensure that the acceptance of an input does not depend on the way how the input is read. The paper studies the constructions of biautomata from the descriptional point of view. It proves the tight bounds on the size of a biautomaton recognizing a regular language represented by a deterministic or nondeterministic automaton.

Název v anglickém jazyce

Descriptional Complexity of Biautomata

Popis výsledku anglicky

A biautomaton is a finite automaton which arbitrarily alternates between reading the input word from the left and from the right. Some compatibility assumptions in the formal definition of a biautomaton ensure that the acceptance of an input does not depend on the way how the input is read. The paper studies the constructions of biautomata from the descriptional point of view. It proves the tight bounds on the size of a biautomaton recognizing a regular language represented by a deterministic or nondeterministic automaton.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

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í

2012

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 statě ve sborníku

Descriptional Complexity of Formal Systems

ISBN

9783642316227

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

196-208

Název nakladatele

Springer-Verlag Berlin Heidelberg

Místo vydání

Berlin Heidelberg

Místo konání akce

Braga, Portugal

Datum konání akce

1. 1. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—