uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The complexity of regular abstractions of one-counter languages
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Max Planck Inst Software Syst MPI SWS, Kaiserslautern, Germany..
Univ Paris Saclay, CNRS, LSV, St Aubin, France.;Univ Paris Saclay, ENS Cachan, St Aubin, France..
Chennai Math Inst, Madras, Tamil Nadu, India..
Vise andre og tillknytning
2016 (engelsk)Inngår i: Proceedings Of The 31St Annual ACM-IEEE Symposium On Logic In Computer Science (LICS 2016), 2016, s. 207-216Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language L (A) : its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown whether appropriate NFA of sub-exponential size exist.

sted, utgiver, år, opplag, sider
2016. s. 207-216
Emneord [en]
one-counter automata, upward closure, downward closure, Parikh image
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-311416DOI: 10.1145/2933575.2934561ISI: 000387609200021ISBN: 9781450343916 (tryckt)OAI: oai:DiVA.org:uu-311416DiVA, id: diva2:1060009
Konferanse
31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS), JUL 05-08, 2016, New York City, NY
Tilgjengelig fra: 2016-12-27 Laget: 2016-12-27 Sist oppdatert: 2018-01-13bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Atig, Mohamed Faouzi

Søk i DiVA

Av forfatter/redaktør
Atig, Mohamed Faouzi
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 419 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf