All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Boolean functions with long prime implicants

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10144055" target="_blank" >RIV/00216208:11320/13:10144055 - isvavai.cz</a>

  • Result on the web

    <a href="http://dx.doi.org/10.1016/j.ipl.2013.07.001" target="_blank" >http://dx.doi.org/10.1016/j.ipl.2013.07.001</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.ipl.2013.07.001" target="_blank" >10.1016/j.ipl.2013.07.001</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Boolean functions with long prime implicants

  • Original language description

    In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, itis possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

  • CEP classification

    IN - Informatics

  • OECD FORD branch

Result continuities

  • Project

    <a href="/en/project/GAP202%2F10%2F1188" target="_blank" >GAP202/10/1188: KnowSched: Knowledge Techniques in Scheduling</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2013

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Name of the periodical

    Information Processing Letters

  • ISSN

    0020-0190

  • e-ISSN

  • Volume of the periodical

    113

  • Issue of the periodical within the volume

    19-21

  • Country of publishing house

    NL - THE KINGDOM OF THE NETHERLANDS

  • Number of pages

    6

  • Pages from-to

    698-703

  • UT code for WoS article

    000325308700002

  • EID of the result in the Scopus database