Complexities for jumps and sweeps

MaRDI QIDQ5867520zbMATH OpenFDO

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

zbMATH Keywords

complexityfinite automatanon-contiguous processingone-way jumping automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

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

Cited in

(5)

• Jump complexity of deterministic finite automata with translucent letters
• 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)