Decision problems for convex languages

DOI10.1016/J.IC.2010.11.009MaRDI QIDQ553302zbMATH OpenOpenAlexFDO

Authors Zhi Xu, Janusz Brzozowski, Jeffrey Shallit

Publication date 27 July 2011

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2010.11.009

zbMATH Keywords

complexityconvex languagefinite automatonidealprefix-freeregular languagesuffix-free

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Decision Problems for Convex Languages
• Complexity in convex languages
• Nondeterministic complexity in subclasses of convex languages
• Complexity of proper prefix-convex regular languages
• Nondeterministic complexity of operations on free and convex languages

Cites work

• A note on multiple-entry finite automata
• Codes and automata.
• Computational Parallels between the Regular and Context-Free Languages
• Decision Problems for Convex Languages
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 15264 (Why is no real title available?)
• scientific article; zbMATH DE number 50943 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 522835 (Why is no real title available?)
• scientific article; zbMATH DE number 1998341 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3416974 (Why is no real title available?)
• Hypercodes
• INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
• Introduction to algorithms.
• Languages convex with respect to binary relations, and their closure properties
• Morphisms preserving densities
• Multiple-entry finite automata
• On free monoids partially ordered by embedding
• On NFAs where all states are final, initial, or both
• Regular expressions: new results and open problems
• Relations on free monoids, their independent sets, and codes¹
• Some remarks on multiple-entry finite automata
• Space-bounded reducibility among combinatorial problems
• Ultimate-Definite and Symmetric-Definite Events and Automata

Cited in

(11)

• Problems on finite automata and the exponential time hypothesis
• Syntactic complexity of suffix-free languages
• Checking whether an automaton is monotonic is NP-complete
• Decision Problems for Convex Languages
• Convex and anti-convex languages
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages
• Decision problems for subregular classes
• Syntactic complexity of regular ideals
• Language membership problems for subregular classes
• On the state complexity of closures and interiors of regular languages with subwords and superwords

This page was built for publication: Decision problems for convex languages

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