scientific article; zbMATH DE number 7439745

MaRDI QIDQ5015284zbMATH OpenFDO

Authors Yoshiki Nakamura

Publication date 7 December 2021

Full work available at URL https://arxiv.org/abs/1609.04101, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2016.19

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Asymptotic approximation by regular languages
• Approximating probabilistic automata by regular languages
• Towards a theory of complexity of regular languages
• scientific article; zbMATH DE number 3856433
• Concise representations of regular languages by degree and probabilistic finite automata
• On the Complexity of the Equivalence Problem for Probabilistic Automata
• On the accuracy of rough approximations of regular languages
• Rough approximations in varieties of regular languages
• scientific article; zbMATH DE number 3390659
• scientific article; zbMATH DE number 3860398

Cites work

• A concrete approach to classical analysis
• Characterizing regular languages with polynomial densities
• Codes and automata.
• Elements of automata theory. Translated from the French by Reuben Thomas
• Elements of finite model theory.
• Experimental descriptive complexity
• From equivalence to almost-equivalence, and beyond-minimizing automata with errors (extended abstract)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 7438576 (Why is no real title available?)
• scientific article; zbMATH DE number 238432 (Why is no real title available?)
• scientific article; zbMATH DE number 3415406 (Why is no real title available?)
• scientific article; zbMATH DE number 3057871 (Why is no real title available?)
• Hyper-Minimization in O(n 2)
• Hyper-minimizing minimized deterministic finite state automata
• Nondeterministic Space is Closed under Complementation
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Programming Techniques: Regular expression search algorithm
• Space-bounded reducibility among combinatorial problems
• The complexity of theorem-proving procedures
• The method of forced enumeration for nondeterministic automata
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• Concise representations of regular languages by degree and probabilistic finite automata
• scientific article; zbMATH DE number 5200941 (Why is no real title available?)
• Monotonicity characterizations of regular languages
• Monotonicity characterizations of regular languages
• Asymptotic approximation by regular languages

This page was built for publication:

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