On Complementation of Nondeterministic Finite Automata without Full Determinization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F26%3A0198409" target="_blank" >RIV/00216305:26230/26:0198409 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-032-04700-7_17" target="_blank" >10.1007/978-3-032-04700-7_17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Complementation of Nondeterministic Finite Automata without Full Determinization

Popis výsledku v původním jazyce

Complementation of finite automata is a basic operation used in numerous applications. The standard way to complement a nondeterministic finite automaton (NFA) is to transform it into an equivalent deterministic finite automaton (DFA) and complement the DFA. The DFA can, however, be exponentially larger than the corresponding NFA. In this paper, we study several alternative approaches to complementation, which are based either on reverse powerset construction or on two novel constructions that exploit a commonly occurring structure of NFAs. Our experiment on a large data set shows that using a different than the classical approach can, in many cases, yield significantly smaller complements.

Název v anglickém jazyce

On Complementation of Nondeterministic Finite Automata without Full Determinization

Popis výsledku anglicky

Complementation of finite automata is a basic operation used in numerous applications. The standard way to complement a nondeterministic finite automaton (NFA) is to transform it into an equivalent deterministic finite automaton (DFA) and complement the DFA. The DFA can, however, be exponentially larger than the corresponding NFA. In this paper, we study several alternative approaches to complementation, which are based either on reverse powerset construction or on two novel constructions that exploit a commonly occurring structure of NFAs. Our experiment on a large data set shows that using a different than the classical approach can, in many cases, yield significantly smaller complements.

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2025

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ů