Han Yo-Sub; Salomaa Arto; Salomaa Kai: Ambiguity, nondeterminism and state complexity of finite automata. In: Acta cybernetica, (23) 1. pp. 141-157. (2017)
Előnézet |
Cikk, tanulmány, mű
actacyb_23_1_2017_9.pdf Letöltés (363kB) | Előnézet |
Absztrakt (kivonat)
The degree of ambiguity counts the number of accepting computations of a nondeterministic finite automaton (NFA) on a given input. Alternatively, the nondeterminism of an NFA can be measured by counting the amount of guessing in a single computation or the number of leaves of the computation tree on a given input. This paper surveys work on the degree of ambiguity and on various nondeterminism measures for finite automata. In particular, we focus on state complexity comparisons between NFAs with quantified ambiguity or nondeterminism.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2017 |
| Kötet: | 23 |
| Szám: | 1 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 141-157 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/50021/ |
| DOI: | 10.14232/actacyb.23.1.2017.9 |
| Kulcsszavak: | Automaták elmélete - véges, Algebra, Véges automaták, Matematikai logika |
| Megjegyzések: | Bibliogr.: p. 154-157. és a lábjegyzetekben |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.01. Matematika 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2018. feb. 12. 09:19 |
| Utolsó módosítás: | 2022. jún. 20. 14:57 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/50067 |
 |
Tétel nézet |
