---
_id: '10052'
abstract:
- lang: eng
  text: "A deterministic finite automaton (DFA) \U0001D49C is composite if its language
    L(\U0001D49C) can be decomposed into an intersection ⋂_{i = 1}^k L(\U0001D49C_i)
    of languages of smaller DFAs. Otherwise, \U0001D49C is prime. This notion of primality
    was introduced by Kupferman and Mosheiff in 2013, and while they proved that we
    can decide whether a DFA is composite, the precise complexity of this problem
    is still open, with a doubly-exponential gap between the upper and lower bounds.
    In this work, we focus on permutation DFAs, i.e., those for which the transition
    monoid is a group. We provide an NP algorithm to decide whether a permutation
    DFA is composite, and show that the difficulty of this problem comes from the
    number of non-accepting states of the instance: we give a fixed-parameter tractable
    algorithm with the number of rejecting states as the parameter. Moreover, we investigate
    the class of commutative permutation DFAs. Their structural properties allow us
    to decide compositionality in NL, and even in LOGSPACE if the alphabet size is
    fixed. Despite this low complexity, we show that complex behaviors still arise
    in this class: we provide a family of composite DFAs each requiring polynomially
    many factors with respect to its size. We also consider the variant of the problem
    that asks whether a DFA is k-factor composite, that is, decomposable into k smaller
    DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation
    DFAs, restricting the number of factors makes the decision computationally harder,
    and yields a problem with tight bounds: it is NP-complete. Finally, we show that
    in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton
    alphabet."
acknowledgement: "Ismaël Jecker: Marie Skłodowska-Curie Grant Agreement No. 754411.
  Nicolas Mazzocchi: BOSCO project PGC2018-102210-B-I00 (MCIU/AEI/FEDER, UE), BLOQUESCM
  project S2018/TCS-4339, and MINECO grant RYC-2016-20281.\r\nPetra Wolf : DFG project
  FE 560/9-1.\r\n"
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ismael R
  full_name: Jecker, Ismael R
  id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  last_name: Jecker
- first_name: Nicolas
  full_name: Mazzocchi, Nicolas
  last_name: Mazzocchi
- first_name: Petra
  full_name: Wolf, Petra
  last_name: Wolf
citation:
  ama: 'Jecker IR, Mazzocchi N, Wolf P. Decomposing permutation automata. In: <i>32nd
    International Conference on Concurrency Theory</i>. Vol 203. Schloss Dagstuhl
    - Leibniz Zentrum für Informatik; 2021. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2021.18">10.4230/LIPIcs.CONCUR.2021.18</a>'
  apa: 'Jecker, I. R., Mazzocchi, N., &#38; Wolf, P. (2021). Decomposing permutation
    automata. In <i>32nd International Conference on Concurrency Theory</i> (Vol.
    203). Paris, France: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2021.18">https://doi.org/10.4230/LIPIcs.CONCUR.2021.18</a>'
  chicago: Jecker, Ismael R, Nicolas Mazzocchi, and Petra Wolf. “Decomposing Permutation
    Automata.” In <i>32nd International Conference on Concurrency Theory</i>, Vol.
    203. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2021.18">https://doi.org/10.4230/LIPIcs.CONCUR.2021.18</a>.
  ieee: I. R. Jecker, N. Mazzocchi, and P. Wolf, “Decomposing permutation automata,”
    in <i>32nd International Conference on Concurrency Theory</i>, Paris, France,
    2021, vol. 203.
  ista: 'Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd
    International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
    Theory, LIPIcs, vol. 203, 18.'
  mla: Jecker, Ismael R., et al. “Decomposing Permutation Automata.” <i>32nd International
    Conference on Concurrency Theory</i>, vol. 203, 18, Schloss Dagstuhl - Leibniz
    Zentrum für Informatik, 2021, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2021.18">10.4230/LIPIcs.CONCUR.2021.18</a>.
  short: I.R. Jecker, N. Mazzocchi, P. Wolf, in:, 32nd International Conference on
    Concurrency Theory, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
  end_date: 2021-08-27
  location: Paris, France
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2021-08-23
date_created: 2021-09-27T14:33:14Z
date_published: 2021-08-13T00:00:00Z
date_updated: 2022-05-13T08:12:52Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2021.18
ec_funded: 1
external_id:
  arxiv:
  - '2107.04683'
file:
- access_level: open_access
  checksum: 4722c81be82265cf45e78adf9db91250
  content_type: application/pdf
  creator: cchlebak
  date_created: 2021-10-01T11:10:53Z
  date_updated: 2021-10-01T11:10:53Z
  file_id: '10064'
  file_name: 2021_CONCUR_Jecker.pdf
  file_size: 1003552
  relation: main_file
  success: 1
file_date_updated: 2021-10-01T11:10:53Z
has_accepted_license: '1'
intvolume: '       203'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 32nd International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - 978-3-9597-7203-7
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decomposing permutation automata
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 203
year: '2021'
...