Complexities for jumps and sweeps

MaRDI QIDQ5867520FDOQ5867520

Authors: Szilárd Zsolt Fazekas, Robert Mercaş, Olivia Wu 

Publication date: 14 September 2022

Full work available at URL: http://www.jalc.de/issues/2022/issue_27_1-3/jalc-2022-131-149.php

Recommendations

• One-way jumping finite automata
• Characterization and complexity results on jumping finite automata
• Two-way deterministic automata with jumping mode
• Jumping finite automata: characterizations and complexity
• The effect of jumping modes on various automata models

zbMATH Keywords

complexityfinite automatanon-contiguous processingone-way jumping automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Queue Automata: Foundations and Developments
• Two-dimensional jumping finite automata
• Jumping finite automata
• Nondeterministic right one-way jumping finite automata
• Jumping finite automata: characterizations and complexity
• One-way jumping finite automata
• Properties of right one-way jumping finite automata
• Decidability of right one-way jumping finite automata
• Two-way deterministic automata with jumping mode

Cited In (4)

• Jump complexity of finite automata with translucent letters
• Sweep complexity revisited
• Freezing 1-Tag Systems with States
• On the Degree of Extension of Some Models Defining Non-Regular Languages

This page was built for publication: Complexities for jumps and sweeps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5867520)