Nondeterministic right one-way jumping finite automata
| Autor: | Markus Holzer, Simon Beier |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Theoretical computer science
Finite-state machine Process (engineering) Computer science 0102 computer and information sciences 02 engineering and technology medicine.disease_cause 01 natural sciences Computer Science Applications Theoretical Computer Science Nondeterministic algorithm Jumping Computational Theory and Mathematics 010201 computation theory & mathematics Subject (grammar) 0202 electrical engineering electronic engineering information engineering medicine Natural (music) 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory Information Systems |
| Zdroj: | Information and Computation. 284:104687 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2021.104687 |
| Popis: | Right-one way jumping finite automata are deterministic devices that process their input in a discontinuous fashion. We generalise these devices to nondeterministic machines. More precisely we study the impact on the computational power of these machines when allowing multiple initial states and/or a nondeterministic transition function including spontaneous or λ-transitions. We show inclusion relations and incomparability results of the induced language families. Since for right-one way jumping devices the use of spontaneous transitions is subject to different natural interpretations, we also study this subject in detail, showing that most interpretations are equivalent to each other and lead to the same language families. Finally we also study inclusion and incomparability results to classical language families and to the families of languages accepted by finite automata with translucent letters. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect