Nondeterministic state complexity of proportional removals

DOI10.1142/S0129054114400103MaRDI QIDQ5173288zbMATH OpenFDO

Authors Daniel Goč, Alexandros Palioudakis, Kai Salomaa

Publication date 9 February 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054114400103

zbMATH Keywords

finite automatanondeterminismproportional removalsstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Nondeterministic state complexity of proportional removals
• scientific article; zbMATH DE number 2068872
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Nondeterministic state complexity for suffix-free regular languages
• State Complexity of Deletion

Cites work

• Descriptional and computational complexity of finite automata -- a survey
• Finite automata and unary languages
• Intersection and union of regular languages and state complexity
• Minimal NFA Problems are Hard
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On pseudo‐polynomials
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Regularity-preserving relations
• The state complexities of some basic operations on regular languages

Cited in

(4)

• Nondeterministic state complexity of proportional removals
• State Complexity of Deletion
• scientific article; zbMATH DE number 2068872 (Why is no real title available?)
• Further closure properties of input-driven pushdown automata

This page was built for publication: Nondeterministic state complexity of proportional removals

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