Jump complexity of finite automata with translucent letters

DOI10.1016/j.tcs.2024.114450OpenAlexW4391756026MaRDI QIDQ6190004

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

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

regular languagejump complexityautomata with translucent letterssublinear jump complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of sweeping automata
• Finite automata with multiplication
• Remarks on blind and partially blind one-way multicounter machines
• On the degrees of non-regularity and non-context-freeness
• On the group memory complexity of extended finite automata over groups
• CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages
• Alternation
• JUMPING FINITE AUTOMATA
• Developments in Language Theory
• On Relations Defined by Generalized Finite Automata
• On Multi-Head Finite Automata
• One-Way Jumping Finite Automata
• Extended finite automata over groups