About: Boolean functions with long prime implicants

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Boolean functions with long prime implicants Goto Sponge Distinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1016/j.ipl.2013.07.001
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, it is 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. 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, it is 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. (en)
Title	Boolean functions with long prime implicants Boolean functions with long prime implicants (en)
skos:prefLabel	Boolean functions with long prime implicants Boolean functions with long prime implicants (en)
skos:notation	RIV/00216208:11320/13:10144055!RIV14-GA0-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GAP202/10/1188)
http://linked.open...iv/cisloPeriodika	19-21
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Kučera, Petr Čepek, Ondřej
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	63738
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/13:10144055
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Set cover; Consensus method; DNF; Boolean minimization; Approximation algorithms; Analysis of algorithms (en)
http://linked.open.../riv/klicoveSlovo	Boolean minimization Analysis of algorithms Approximation algorithms Consensus method DNF Set cover
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[2727EE8B97B4]
http://linked.open...i/riv/nazevZdroje	Information Processing Letters
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	KnowSched: Knowledge Techniques in Scheduling
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	113
http://linked.open...iv/tvurceVysledku	Kučera, Petr Čepek, Ondřej Kuřík, Stanislav
http://linked.open...ain/vavai/riv/wos	000325308700002
issn	0020-0190
number of pages	6 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.ipl.2013.07.001
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 53 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software