The membership problem for linear and regular permutation languages

DOI10.1007/978-3-319-22360-5_18MaRDI QIDQ2947424zbMATH OpenOpenAlexFDO

Authors Grzegorz Madejski

Publication date 23 September 2015

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-22360-5_18

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• On the membership problem of permutation grammars -- a direct proof of NP-completeness
• On the membership problem for finite automata over symmetric groups
• Regular and linear permutation languages
• ON A HIERARCHY OF PERMUTATION LANGUAGES
• Infinite hierarchy of permutation languages

Cited in

(12)

• Membership problems for regular and context-free trace languages
• On the membership problem for finite automata over symmetric groups
• The magic number problem for subregular language families
• Regular languages of plus- and minus-(in)decomposable permutations
• Orbits of linear maps and properties of regular languages
• ON A HIERARCHY OF PERMUTATION LANGUAGES
• Optimal regular expressions for permutations
• Regular and linear permutation languages
• The membership problem for unordered vector languages
• On the membership problem of permutation grammars -- a direct proof of NP-completeness
• Principles and Practice of Constraint Programming – CP 2004
• Permutation rewriting and algorithmic verification

This page was built for publication: The membership problem for linear and regular permutation languages

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