Jump complexity of finite automata with translucent letters

DOI10.1016/J.TCS.2024.114450MaRDI QIDQ6190004zbMATH OpenOpenAlexFDO

Authors Victor Mitrana, Andrei Păun, Mihaela Păun, Jose Ramon Sanchez Couso

Publication date 5 March 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2024.114450

zbMATH Keywords

automata with translucent lettersjump complexityregular languagesublinear jump complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Characterization and complexity results on jumping finite automata
• Operational state complexity and decidability of jumping finite automata
• Operational state complexity and decidability of jumping finite automata
• Jumping finite automata: characterizations and complexity
• Jumping finite automata

Cites work

• Alternation
• CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages
• Complexities for jumps and sweeps
• Developments in Language Theory
• Extended finite automata over groups
• Finite automata with multiplication
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• Jumping finite automata
• Lower bounds on the size of sweeping automata
• On Multi-Head Finite Automata
• On Relations Defined by Generalized Finite Automata
• On the degrees of non-regularity and non-context-freeness
• On the group memory complexity of extended finite automata over groups
• One-way jumping finite automata
• Remarks on blind and partially blind one-way multicounter machines

Cited in

(9)

• Non-returning deterministic and nondeterministic finite automata with translucent letters
• Non-returning finite automata with translucent letters
• On properties of languages accepted by deterministic pushdown automata with translucent input letters
• Subsequence matching and analysis problems for automata with translucent letters
• Deterministic pushdown automata with translucent input letters
• Jump complexity of deterministic finite automata with translucent letters
• Deterministic pushdown automata with translucent input letters
• On properties of languages accepted by deterministic pushdown automata with translucent input letters
• Subsequence matching and analysis problems for formal languages

This page was built for publication: Jump complexity of finite automata with translucent letters

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