Decision problems for convex languages

DOI10.1016/j.ic.2010.11.009zbMath1217.68125OpenAlexW2676854164MaRDI QIDQ553302

Zhi Xu, Janusz A. Brzozowski, Jeffrey O. 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

complexityidealregular languagefinite automatonprefix-freesuffix-freeconvex language

Mathematics Subject Classification ID

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

Related Items (9)

Problems on finite automata and the exponential time hypothesis ⋮ Quotient complexity of closed languages ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Syntactic complexity of suffix-free languages ⋮ Syntactic complexity of regular ideals ⋮ Decision Problems for Convex Languages ⋮ Complexity of bifix-free regular languages ⋮ Complexity of bifix-free regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On NFAs where all states are final, initial, or both
• Space-bounded reducibility among combinatorial problems
• A note on multiple-entry finite automata
• Some remarks on multiple-entry finite automata
• Multiple-entry finite automata
• Decision Problems for Convex Languages
• Relations on free monoids, their independent sets, and codes¹
• Computational Parallels between the Regular and Context-Free Languages
• Morphisms preserving densities
• Hypercodes
• INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
• Ultimate-Definite and Symmetric-Definite Events and Automata
• On free monoids partially ordered by embedding
• Depth-First Search and Linear Graph Algorithms

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