On Usefulness of Information: Framework and NFA Case

DOI10.1007/978-3-319-98355-4_6zbMath1514.68110OpenAlexW2886905877MaRDI QIDQ6163619

Šimon Sádovský, Branislav Rovan

Publication date: 30 June 2023

Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-98355-4_6

zbMATH Keywords

advicestate complexitysupplementary informationdescriptional complexitynondeterministic finite automatausefulness of informationdecomposition of finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Usefulness of information and decomposability of unary regular languages ⋮ Usefulness of information and unary languages

Cites Work

• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Modeling time criticality of information
• Simplifying DPDA Using Supplementary Information
• Information Complexity of Online Problems
• The complexity of promise problems with applications to public-key cryptography
• On the Hardness of Reoptimization
• How Much Information about the Future Is Needed?
• Assisted Problem Solving and Decompositions of Finite Automata

This page was built for publication: On Usefulness of Information: Framework and NFA Case