Jump complexity of finite automata with translucent letters

DOI10.1016/J.TCS.2024.114450OpenAlexW4391756026MaRDI QIDQ6190004FDOQ6190004

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

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

zbMATH Keywords

regular languagejump complexityautomata with translucent letterssublinear jump complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Alternation
• On Relations Defined by Generalized Finite Automata
• On Multi-Head Finite Automata
• Remarks on blind and partially blind one-way multicounter machines
• Lower bounds on the size of sweeping automata
• CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages
• Title not available (Why is that?)
• Extended finite automata over groups
• Developments in Language Theory
• Finite automata with multiplication
• Jumping 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
• Title not available (Why is that?)

Cited In (3)

• 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

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)