Search results for "definability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
92	Johann A. Makowsky	Invariant Definability and P/poly.	CSL	1998	DBLP DOI BibTeX RDF
72	Alexej P. Pynko	A relative interpolation theorem for infinitary universal Horn logic and its applications.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF	Universal Horn theory, Interpolation theorem, Preservation theorem, Definability theorem
67	Margarita V. Korovina	Computational Aspects of sigma-Definability over the Real Numbers without the Equality Test.	CSL	2003	DBLP DOI BibTeX RDF
67	Anuj Dawar, Lauri Hella, Phokion G. Kolaitis	Implicit Definability and Infinitary Logic in Finite Model Theory.	ICALP	1995	DBLP DOI BibTeX RDF
63	Alfredo Burrieza, Inman P. de Guzmán	A Temporal × Modal Approach to the Definability of Properties of Functions.	FroCoS	2002	DBLP DOI BibTeX RDF	$Ttimes W$-semantics, functional semantics, completeness, definability
54	Yiyu Yao	A Note on Definability and Approximations.	Trans. Rough Sets	2007	DBLP DOI BibTeX RDF
54	Jerzy W. Grzymala-Busse, Wojciech Rzasa	Definability of Approximations for a Generalization of the Indiscernibility Relation.	FOCI	2007	DBLP DOI BibTeX RDF
54	Leonid Libkin, Frank Neven	Logical Definability and Query Languages over Unranked Trees.	LICS	2003	DBLP DOI BibTeX RDF
54	Damon Kaller	Definability Equals Recognizability of Partial 3-Trees.	WG	1996	DBLP DOI BibTeX RDF
50	Oleg V. Kudinov, Victor L. Selivanov	Definability in the Infix Order on Words.	Developments in Language Theory	2009	DBLP DOI BibTeX RDF	Infix order, least fixed point, biinterpretability, definability, automorphism, first-order theory
50	Oleg V. Kudinov, Victor L. Selivanov	A Gandy Theorem for Abstract Structures and Applications to First-Order Definability.	CiE	2009	DBLP DOI BibTeX RDF	Gandy theorem, least fixed point, biinterpretability, labeled forest, h-quasiorder, definability
50	Marc Aiguier, Fabrice Barbier	An Institution-independent Proof of the Beth Definability Theorem.	Stud Logica	2007	DBLP DOI BibTeX RDF	Beth definability, morphisms and comorphisms, inclusive category, institution theory, Craig interpolation
50	Larisa Maksimova	Definability and Interpolation in Non-Classical Logics.	Stud Logica	2006	DBLP DOI BibTeX RDF	interpolation, modal logic, intuitionistic logic, definability, non-classical logics, amalgamation
50	Elisabeth Pelz	About the concurrent behaviour of EN systems: definability and closure results.	European Workshop on Applications and Theory in Petri Nets	1988	DBLP DOI BibTeX RDF	concurrent behaviour, partial word languages, logical specifications, monadic second order logic, definability, Elementary net systems
47	Matthias Baaz, Rosalie Iemhoff	On Interpolation in Existence Logics.	LPAR	2005	DBLP DOI BibTeX RDF	existence predicate, Gentzen calculus, Beth definability, truth-value logics, Gödel logics, Scott logics, interpolation, cut-elimination, Intuitionistic logic, Kripke models, Skolemization
47	Marcelo P. Fiore	Semantic analysis of normalisation by evaluation for typed lambda calculus.	PPDP	2002	DBLP DOI BibTeX RDF	categorical glueing, lambda definability, normalisation by evaluation, typed abstract syntax with variable binding, logical relations, typed lambda calculus, initial algebra semantics
47	Achim Blumensath, Erich Grädel	Automatic Structures.	LICS	2000	DBLP DOI BibTeX RDF	definability vs. complexity, logic, interpretability, Automata
47	Achim Blumensath	Bounded Arithmetic and Descriptive Complexity.	CSL	2000	DBLP DOI BibTeX RDF	arithmetic, descriptive complexity, definability
41	Xavier Caicedo	Definability and automorphisms in abstract logics.	Arch. Math. Log.	2004	DBLP DOI BibTeX RDF
41	Martin Grohe, Julian Mariño	Definability and Descriptive Complexity on Databases of Bounded Tree-Width.	ICDT	1999	DBLP DOI BibTeX RDF
41	Eugenia Ternovskaia	Inductive Definability and the Situation Calculus.	Transactions and Change in Logic Databases	1998	DBLP DOI BibTeX RDF
41	Wojciech Buszkowski	Approximation Spaces and Definability for Incomplete Information Systems.	Rough Sets and Current Trends in Computing	1998	DBLP DOI BibTeX RDF
41	Stephen A. Fenner, Lance Fortnow, Lide Li	Gap-Definability as a Closure Property.	STACS	1993	DBLP DOI BibTeX RDF
38	Thierry Joly	Encoding of the Halting Problem into the Monster Type & Applications.	TLCA	2003	DBLP DOI BibTeX RDF
38	H. Imhof	Logics that define their own semantics.	Arch. Math. Log.	1999	DBLP DOI BibTeX RDF
38	Anil Seth	Sharper Results on the Expressive Power of Generalized Quantifiers.	FSTTCS	1997	DBLP DOI BibTeX RDF
38	Newton C. A. da Costa, Alexandre A. M. Rodrigues	Definability and Invariance.	Stud Logica	2007	DBLP DOI BibTeX RDF	Generalized Galois Theory, Invariance, Model Theory, Definability, Galois Theory
38	Oleg V. Kudinov, Victor L. Selivanov	Definability in the Homomorphic Quasiorder of Finite Labeled Forests.	CiE	2007	DBLP DOI BibTeX RDF	homomorphic quasiorder, atomic structure, definability, forest, automorphism, Labeled tree
38	Stefan Kahrs	Limits of ML-Definability.	PLILP	1996	DBLP DOI BibTeX RDF	completeness, ML, polymorphism, recursion, definability
38	Helmut Thiele	On the Mutual Definability of Fuzzy Tolerance Relations and Fuzzy Tolerance Coverings.	ISMVL	1995	DBLP DOI BibTeX RDF	tolerance analysis, mutual definability, fuzzy tolerance relations, fuzzy tolerance coverings, systems of sets, fixed universe, crisp set theory, bijections, fuzzy equivalence relations, crisp tolerance relations, crisp coverings, pattern recognition, cluster analysis, symmetry, fuzzy clusters, fuzzy set theory, equivalence classes, similarity relations, universal algebras, binary relations, reflexivity, fuzzy partitions, lattice isomorphisms
34	Marc Gyssens, Jan Paredaens, Dirk Van Gucht, George H. L. Fletcher	Structural characterizations of the semantics of XPath as navigation tool on a document.	PODS	2006	DBLP DOI BibTeX RDF	XPath, expressibility, definability
34	Ranko Lazic 0001, David Nowak	On a Semantic Definition of Data Independence .	TLCA	2003	DBLP DOI BibTeX RDF	nondeterminism, logical relations, Data independence, definability
34	Victor L. Selivanov	A Logical Approach to Decidability of Hierarchies of Regular Star-Free Languages.	STACS	2001	DBLP DOI BibTeX RDF	Star-free regular languages, hierarchies, decidability, definability
33	Philippe Balbiani, Tinko Tinchev	Decidable and Undecidable Problems for First-Order Definability and Modal Definability.	TbiLLC	2019	DBLP DOI BibTeX RDF
33	Juha Kontinen, Jakub Szymanik	A characterization of definability of second-order generalized quantifiers with applications to non-definability.	J. Comput. Syst. Sci.	2014	DBLP DOI BibTeX RDF
29	Jing Shi	Modal Expressivity and Definability over Sets.	LORI	2009	DBLP DOI BibTeX RDF
29	Michael Benedikt, Leonid Libkin, Frank Neven	Logical definability and query languages over ranked and unranked trees.	ACM Trans. Comput. Log.	2007	DBLP DOI BibTeX RDF	Ranked trees, unranked trees, query languages, tree automata, model theory
29	Margarita V. Korovina, Oleg V. Kudinov	The Uniformity Principle for Sigma -Definability with Applications to Computable Analysis.	CiE	2007	DBLP DOI BibTeX RDF
29	Jan Rauch	Definability of Association Rules in Predicate Calculus.	Foundations and Novel Approaches in Data Mining	2006	DBLP DOI BibTeX RDF
29	Clemens Grabmayer, Jan Willem Klop, Bas Luttik	Some Remarks on Definability of Process Graphs.	CONCUR	2006	DBLP DOI BibTeX RDF
29	Albert Atserias	Definability on a Random 3-CNF Formula.	LICS	2005	DBLP DOI BibTeX RDF
29	Martin Grohe, György Turán	Learnability and Definability in Trees and Similar Structures.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
29	Margarita V. Korovina	Recent Advances in S-Definability over Continuous Data Types.	Ershov Memorial Conference	2003	DBLP DOI BibTeX RDF
29	Dietmar Berwanger, Erich Grädel, Stephan Kreutzer	Once upon a Time in a West - Determinacy, Definability, and Complexity of Path Games.	LPAR	2003	DBLP DOI BibTeX RDF
29	Antonio Bucciarelli, Benjamin Leperchey, Vincent Padovani	Relative Definability and Models of Unary PCF.	TLCA	2003	DBLP DOI BibTeX RDF
29	Massimo Franceschet, Angelo Montanari, Adriano Peron, Guido Sciavicco	Definability and decidability of binary predicates for time granularity.	TIME	2003	DBLP DOI BibTeX RDF
29	Mauro Ferrari 0002, Camillo Fiorentini, Guido Fiorino	On the Complexity of Disjunction and Explicit Definability Properties in Some Intermediate Logics.	LPAR	2002	DBLP DOI BibTeX RDF
29	Martin Grohe, György Turán	Learnability and Definability in Trees and Similar Structures.	STACS	2002	DBLP DOI BibTeX RDF
29	Lotfi A. Zadeh	Toward a Theory of Hierarchical Definability (THD).	Rough Sets and Current Trends in Computing	2002	DBLP DOI BibTeX RDF
29	Alexandra Shlapentokh	Diophantine definability over non-finitely generated non-degenerate modules of algebraic extensions of Q.	Arch. Math. Log.	2001	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03C57, 03D35, 11D57, 11U05
29	Foto N. Afrati, Hans Leiß, Michel de Rougemont	Definability and Compression.	LICS	2000	DBLP DOI BibTeX RDF	Lempel-Ziv, compression, logic
29	Michael Benedikt, H. Jerome Keisler	Definability over Linear Constraints.	CSL	2000	DBLP DOI BibTeX RDF
29	Eva Hoogland, Maarten Marx, Martin Otto 0001	Beth Definability for the Guarded Fragment.	LPAR	1999	DBLP DOI BibTeX RDF
29	Marcelo P. Fiore, Alex K. Simpson	Lambda Definability with Sums via Grothendieck Logical Relations.	TLCA	1999	DBLP DOI BibTeX RDF
29	Helmut Thiele	On the Mutual Definability of Classes of Generalized Fuzzy Implications and of Classes of Generalized NegationsandS-Norms.	ISMVL	1997	DBLP DOI BibTeX RDF	S-implications, S-norms, R-implications, QL-implications, negations, T-norms
29	Arnold L. Rosenberg	On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages.	J. ACM	1968	DBLP DOI BibTeX RDF
25	Christian Glaßer, Stephen D. Travers	Machines that Can Output Empty Words.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Leaf languages, Gap theorems, Computational complexity, Polynomial-time hierarchy
25	Martin Grohe	Definable Tree Decompositions.	LICS	2008	DBLP DOI BibTeX RDF	fixed point logic, descriptive complexity, tree decomposition
25	Albert Atserias, Andrei A. Bulatov, Anuj Dawar	Affine Systems of Equations and Counting Infinitary Logic.	ICALP	2007	DBLP DOI BibTeX RDF
25	Yiyu Yao, Yaohua Chen	Rough Set Approximations in Formal Concept Analysis.	Trans. Rough Sets	2006	DBLP DOI BibTeX RDF
25	Christian Glaßer, Stephen D. Travers	Machines that Can Output Empty Words.	MFCS	2006	DBLP DOI BibTeX RDF
25	Margarita V. Korovina, Oleg V. Kudinov	Towards Computability of Higher Type Continuous Data.	CiE	2005	DBLP DOI BibTeX RDF
25	Kerkko Luosto	Equicardinality on Linear Orders.	LICS	2004	DBLP DOI BibTeX RDF
25	Ramon Jansana	Leibniz Filters Revisited.	Stud Logica	2003	DBLP DOI BibTeX RDF	Weakly algebraizable logics, global and local consequence relations, Protoalgebraic logics
25	Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi	Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.	CP	2002	DBLP DOI BibTeX RDF
25	Martin Otto 0001	The Logic of Explicitly Presentation-Invariant Circuits.	CSL	1996	DBLP DOI BibTeX RDF	generic computation, Circuit complexity, finite model theory
25	Marek Zaionc	Lambda Representation of Operations Between Fifferent Term Algebras.	CSL	1994	DBLP DOI BibTeX RDF
25	Stéphane Grumbach	A Paradox in Database Theory.	ICDT	1992	DBLP DOI BibTeX RDF
25	Uschi Heuter	First-Order Properties of Trees, Star-Free Expressions, adn Aperiodicity.	STACS	1988	DBLP DOI BibTeX RDF
25	Daniel Leivant, Tim Fernando	Skinny and Fleshy Failures of Relative Completeness.	POPL	1987	DBLP DOI BibTeX RDF
21	Balder ten Cate, Phokion G. Kolaitis	Structural characterizations of schema-mapping languages.	ICDT	2009	DBLP DOI BibTeX RDF	data integration, data exchange, schema mapping, definability
21	Juha Kontinen, Jakub Szymanik	A Remark on Collective Quantification.	J. Log. Lang. Inf.	2008	DBLP DOI BibTeX RDF	Collective quantification, Lindström quantifiers, Second-order generalized quantifiers, Type-shifting, Computational complexity, Definability
21	Maarten Marx	Queries determined by views: pack your views.	PODS	2007	DBLP DOI BibTeX RDF	views, query rewriting, definability, guarded fragment
21	Willem J. Blok, Eva Hoogland	The Beth Property in Algebraic Logic.	Stud Logica	2006	DBLP DOI BibTeX RDF	equivalential logics, Beth definability property, epimorphisms, algebraizable logics, Abstract algebraic logic
21	Michael Benedikt, Leonid Libkin, Thomas Schwentick, Luc Segoufin	Definable relations and first-order query languages over strings.	J. ACM	2003	DBLP DOI BibTeX RDF	first-order definability, query languages, Strings, expressive power, quantifier elimination
21	Johan van Benthem	Time, logic and computation.	REX Workshop	1988	DBLP DOI BibTeX RDF	first-order definability, period structure, point structure, Completeness, correspondence, event structure, temporal operator, computational semantics, tense logic
21	Patrick Bellot	Unformly Applicative Structures, A Theory of Computability and Polyadic Functions.	FSTTCS	1988	DBLP DOI BibTeX RDF	polyadicity, algorithmic, abstraction, computability, representability, recursive function, definability
16	Gabriel Goldberg	Strongly compact cardinals and ordinal definability.	J. Math. Log.	2024	DBLP DOI BibTeX RDF
16	Benedikt Pago	Choiceless Computation and Symmetry: Limitations of Definability.	CoRR	2024	DBLP DOI BibTeX RDF
16	Lucas Bueri, Radu Iosif, Florian Zuleger	Effective MSO-Definability for Tree-width Bounded Models of an Inductive Separation Logic of Relations.	CoRR	2024	DBLP DOI BibTeX RDF
16	Jan Heuer, Christoph Wernhard	Synthesizing Strongly Equivalent Logic Programs: Beth Definability for Answer Set Programs via Craig Interpolation in First-Order Logic.	CoRR	2024	DBLP DOI BibTeX RDF
16	Lekshmi Kamal K. Sheela, Manoj Changat, Jeny Jacob	The Weak-Toll Function of a Graph: Axiomatic Characterizations and First-Order Non-definability.	CALDAM	2024	DBLP DOI BibTeX RDF
16	Keith A. Kearnes	Relative Maltsev definability of some commutator properties.	Int. J. Algebra Comput.	2023	DBLP DOI BibTeX RDF
16	Lothar Sebastian Krapp, Salma Kuhlmann, Moritz Link	Definability of Henselian Valuations by conditions on the Value Group.	J. Symb. Log.	2023	DBLP DOI BibTeX RDF
16	Martin Grohe, Daniel Neuen	Canonisation and Definability for Graphs of Bounded Rank Width.	ACM Trans. Comput. Log.	2023	DBLP DOI BibTeX RDF
16	Derek Levinson	John Steel and Hugh Woodin. HOD as a Core Model. Ordinal Definability and Recursion Theory: The Cabal Seminar, Volume III, edited by Alexander Kechris, Benedikt Lowe, and John Steel, Lecture Notes in Logic, vol. 3, Cambridge University Press, Cambridge, pp. 257-345.	Bull. Symb. Log.	2023	DBLP DOI BibTeX RDF
16	Juha Kontinen, Yasir Mahmood 0002, Arne Meier, Heribert Vollmer	Parameterized Complexity of Weighted Team Definability.	CoRR	2023	DBLP DOI BibTeX RDF
16	Miguel Campercholi, Mauricio Tellechea, Pablo Ventura	Two algorithms to decide Quantifier-free Definability in Finite Algebraic Structures.	CoRR	2023	DBLP DOI BibTeX RDF
16	Zoltan A. Kocsis	Proof-theoretic methods in quantifier-free definability.	CoRR	2023	DBLP DOI BibTeX RDF
16	Benedetto Intrigila, Giulio Manzonetto, Nicolas Munnich	Extended Addressing Machines, explicit substitutions, PCF, definability, full abstraction.	CoRR	2023	DBLP DOI BibTeX RDF
16	Dino Mandrioli, Matteo Pradella, Stefano Crespi-Reghizzi	Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages.	Log. Methods Comput. Sci.	2023	DBLP DOI BibTeX RDF
16	Pascal Baumann 0001, Moses Ganardi, Ramanathan S. Thinniyam, Georg Zetzsche	Existential Definability over the Subword Ordering.	Log. Methods Comput. Sci.	2023	DBLP DOI BibTeX RDF
16	Sebastian Maneth, Helmut Seidl, Martin Vu	Definability Results for Top-Down Tree Transducers.	Int. J. Found. Comput. Sci.	2023	DBLP DOI BibTeX RDF
16	Guillermo Badia, Xavier Caicedo, Carles Noguera	Frame definability in finitely valued modal logics.	Ann. Pure Appl. Log.	2023	DBLP DOI BibTeX RDF
16	Farmer Schlutzenberg	The definability of E in self-iterable mice.	Ann. Pure Appl. Log.	2023	DBLP DOI BibTeX RDF
16	Jeny Jacob, Manoj Changat	Segment Transit Function of the Induced Path Function of Graphs and Its First-Order Definability.	ICLA	2023	DBLP DOI BibTeX RDF
16	Jean-Marie Lagniez, Pierre Marquis	Boosting Definability Bipartition Computation Using SAT Witnesses.	JELIA	2023	DBLP DOI BibTeX RDF
16	Alexis Bès, Christian Choffrut	Decidability of Definability Issues in the Theory of Real Addition.	Fundam. Informaticae	2022	DBLP DOI BibTeX RDF
16	Haim Horowitz, Saharon Shelah	κ-Madness and definability.	Math. Log. Q.	2022	DBLP DOI BibTeX RDF
16	Yana Rumenova, Tinko Tinchev	Modal Definability: Two Commuting Equivalence Relations.	Logica Universalis	2022	DBLP DOI BibTeX RDF