Search results for "decidability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
53	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
53	Mark Weyer	Decidability of S1S and S2S.	Automata, Logics, and Infinite Games	2001	DBLP DOI BibTeX RDF
45	Petr Jancar	Selected Ideas Used for Decidability and Undecidability of Bisimilarity.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF	decidability, bisimulation equivalence
45	Mitsuharu Yamamoto, Jean-Marie Cottin, Masami Hagiya	Decidability of Safety Properties of Timed Multiset Rewriting.	FTRTFT	2002	DBLP DOI BibTeX RDF	real-time systems, timed automata, decidability, timed Petri nets
45	Helko Lehmann, Michael Leuschel	Decidability Results for the Propositional Fluent Calculus.	Computational Logic	2000	DBLP DOI BibTeX RDF	reasoning about action and change, fluent calculus, model checking, petri nets, temporal logics, decidability
45	Matteo Baldoni, Laura Giordano 0001, Alberto Martelli	A Tableau for Multimodal Logics and Some (Un)Decidability Results.	TABLEAUX	1998	DBLP DOI BibTeX RDF	Multimodal logics, Prefixed Tableaux methods, Decidability, Formal Grammars
45	Qing Zhou, Weihao Hu	Decidability in Analysis.	Computing	2005	DBLP DOI BibTeX RDF	almost decidable, Decidable
45	Slawomir Lasota 0001	Decidability of Strong Bisimilarity for Timed BPP.	CONCUR	2002	DBLP DOI BibTeX RDF
39	Antje Nowack	A Guarded Fragment for Abstract State Machines.	J. Log. Lang. Inf.	2005	DBLP DOI BibTeX RDF	Datalog LITE, guarded fixed-point logic, computability, decidability, Abstract State Machines, expressive power, guarded fragment
39	Joe Hendrix, Hitoshi Ohsaki	Combining Equational Tree Automata over AC and ACI Theories.	RTA	2008	DBLP DOI BibTeX RDF
39	Alberto Casagrande, Pietro Corvaja, Carla Piazza, Bud Mishra	Composing Semi-algebraic O-Minimal Automata.	HSCC	2007	DBLP DOI BibTeX RDF
39	Colin Stirling	Schema Revisited.	CSL	2000	DBLP DOI BibTeX RDF
37	Sergey Babenyshev, Vladimir V. Rybakov	Decidability of Hybrid Logic with Local Common Knowledge Based on Linear Temporal Logic LTL.	CiE	2008	DBLP DOI BibTeX RDF	multi-agent logics, relational Kripke-Hintikka models, decidability algorithms, satisfiability, linear temporal logic, hybrid logics
37	Davide Bresolin, Valentin Goranko, Angelo Montanari, Guido Sciavicco	On Decidability and Expressiveness of Propositional Interval Neighborhood Logics.	LFCS	2007	DBLP DOI BibTeX RDF	neighbourhood interval logics, decidability, expressiveness
37	Ralf Küsters	On the decidability of cryptographic protocols with open-ended data structures.	Int. J. Inf. Sec.	2005	DBLP DOI BibTeX RDF	Complexity, Cryptographic protocols, Decidability, Transducers
37	Petr Hlinený, Detlef Seese	On Decidability of MSO Theories of Representable Matroids.	IWPEC	2004	DBLP DOI BibTeX RDF	MSO theory, decidability, matroid, branch-width
37	Fabio Balduzzi, Angela Di Febbraro, Alessandro Giua, Carla Seatzu	Decidability results in First-Order Hybrid Petri Nets.	Discret. Event Dyn. Syst.	2001	DBLP DOI BibTeX RDF	hybrid Petri nets, decidability properties, timed automata, hybrid automata
37	Peng Cheng 0009, George J. Pappas, Vijay Kumar 0001	Decidability of Motion Planning with Differential Constraints.	ICRA	2007	DBLP DOI BibTeX RDF
37	Laura Recalde, Serge Haddad, Manuel Silva Suárez	Continuous Petri Nets: Expressive Power and Decidability Issues.	ATVA	2007	DBLP DOI BibTeX RDF
37	Hubert Comon-Lundh, Véronique Cortier	New Decidability Results for Fragments of First-Order Logic and Application to Cryptographic Protocols.	RTA	2003	DBLP DOI BibTeX RDF
37	Colin Stirling	Decidability of Weak Bisimilarity for a Subset of Basic Parallel Processes.	FoSSaCS	2001	DBLP DOI BibTeX RDF
37	Manoranjan Satpathy, Dang Van Hung, Paritosh K. Pandya	Some Decidability Results for Duration Calculus under Synchronous Interpretation.	FTRTFT	1998	DBLP DOI BibTeX RDF
32	Monika Rauch Henzinger, Thomas A. Henzinger, Peter W. Kopke	Computing Simulations on Finite and Infinite Graphs.	FOCS	1995	DBLP DOI BibTeX RDF	simulations computing, infinite graphs, finite graphs, labeled graphs, reactive systems verification, O(mn) algorithm, symbolic similarity-checking procedure, 2D rectangular automata, continuous environments, model-checking problem, graph theory, decidability, decidability, automata theory, similarity relations
32	Robert Beals	Algorithms for Matrix Groups and the Tits Alternative.	FOCS	1995	DBLP DOI BibTeX RDF	finitely generated linear group, nonabelian free group, solvable subgroup, finite index, finitely generated matrix group, nonabelian free subgroups, nilpotent subgroup, encoding length, computational complexity, complexity, encoding, polynomial time algorithm, decidability, decidability, matrix algebra, formal logic, homomorphism, group theory, finite groups, matrix groups, algebraic number field, Las Vegas algorithm, membership testing
32	Lucia Acciai, Michele Boreale	Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types.	ICALP (2)	2009	DBLP DOI BibTeX RDF	behavioural types, safety, decidability, pi-calculus, spatial logic
32	Arne Meier, Martin Mundhenk, Thomas Schneider 0002, Michael Thomas 0001, Volker Weber, Felix Weiss	The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I.	MFCS	2009	DBLP DOI BibTeX RDF	Post’s lattice, complexity, satisfiability, decidability, hybrid logic
32	Renate A. Schmidt, Ullrich Hustadt	The axiomatic translation principle for modal logic.	ACM Trans. Comput. Log.	2007	DBLP DOI BibTeX RDF	Translation approach, small model property, completeness, decidability
32	Martin Fränzle, Michael R. Hansen	Deciding an Interval Logic with Accumulated Durations.	TACAS	2007	DBLP DOI BibTeX RDF	metric-time temporal logic, multi-priced timed automata, Real-time systems, model-checking, decidability
32	Hitoshi Ohsaki, Hiroyuki Seki	Languages Modulo Normalization.	FroCoS	2007	DBLP DOI BibTeX RDF	tree automata modulo axioms, equational rewriting, Boolean closedness, hedge automata and XML schema, regularity, decidability
32	Hitoshi Ohsaki, Jean-Marc Talbot, Sophie Tison, Yves Roos	Monotone AC-Tree Automata.	LPAR	2005	DBLP DOI BibTeX RDF	equational tree automata, complexity, decidability, closure properties
32	Healfdene Goguen	A syntactic approach to eta equality in type theory.	POPL	2005	DBLP DOI BibTeX RDF	beta-eta equality, decidability, type checking, logical frameworks
32	Bernhard Heinemann	Algebras as Knowledge Structures.	MFCS	2005	DBLP DOI BibTeX RDF	modal and hybrid logic, knowledge and algebras, decidability, topological reasoning, reasoning about knowledge
32	Martin Fränzle	Model-checking dense-time Duration Calculus.	Formal Aspects Comput.	2004	DBLP DOI BibTeX RDF	Dense-time Duration Calculus, Model-checking, Decidability
32	Bernhard Heinemann	A Hybrid Logic of Knowledge Supporting Topological Reasoning.	AMAST	2004	DBLP DOI BibTeX RDF	logical frameworks for reasoning, reasoning about knowledge and topology, completeness, decidability, hybridization
32	Martin Fränzle	What Will Be Eventually True of Polynomial Hybrid Automata?	TACS	2001	DBLP DOI BibTeX RDF	State recurrence, Progress properties, Verification procedures, Hybrid systems, Decidability
32	Hitoshi Ohsaki	Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories.	CSL	2001	DBLP DOI BibTeX RDF	decidability, Tree automata, equational theory
31	Petr Jancar, Jirí Srba	Undecidability of bisimilarity by defender's forcing.	J. ACM	2008	DBLP DOI BibTeX RDF	process algebra, undecidability, pushdown automata, Bisimilarity
31	Alberto Casagrande, Pietro Corvaja, Carla Piazza, Bud Mishra	Decidable Compositions of O-Minimal Automata.	ATVA	2008	DBLP DOI BibTeX RDF
31	Christopher A. Stone, Robert Harper 0001	Extensional equivalence and singleton types.	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	equivalence algorithms, logical relations, Singleton types
31	Antje Nowack	Deciding the Verification Problem for Abstract State Machines.	Abstract State Machines	2003	DBLP DOI BibTeX RDF
31	Max I. Kanovich	The Expressive Power of Horn Monadic Linear Logic.	CSL	2001	DBLP DOI BibTeX RDF
31	Jordi Levy	Decidable and Undecidable Second-Order Unification Problems.	RTA	1998	DBLP DOI BibTeX RDF
30	Wei Zhang	On the decidability of open logic.	Sci. China Ser. F Inf. Sci.	2009	DBLP DOI BibTeX RDF	open logic, epistemic process, decidability
30	Chan Le Duc	Decidability of SHI with Transitive Closure of Roles.	ESWC	2009	DBLP DOI BibTeX RDF	OWL, Description Logics, Decidability, Tableaux
30	Ivan Lanese, Jorge A. Pérez 0001, Davide Sangiorgi, Alan Schmitt	On the Expressiveness and Decidability of Higher-Order Process Calculi.	LICS	2008	DBLP DOI BibTeX RDF	behavioral equivalences, decidability, expressiveness, process calculi, higher-order languages
30	Zhenhua Duan, Cong Tian	Decidability of Propositional Projection Temporal Logic with Infinite Models.	TAMC	2007	DBLP DOI BibTeX RDF	infinite model, model checking, satisfiability, decidability, interval temporal logic
30	Alexander Arbieto, Carlos Matheus	Decidability of Chaos for Some Families of Dynamical Systems.	Found. Comput. Math.	2004	DBLP DOI BibTeX RDF	Lyapounov exponents, SRB measures, Topological entropy, Decidability, Chaos
30	Laurent Mazaré	Decidability of Opacity with Non-Atomic Keys.	Formal Aspects in Security and Trust	2004	DBLP DOI BibTeX RDF	Dolev-Yao Constraints, Security, Formal Verification, Decidability, Rewriting Systems, Opacity
30	Géraud Sénizergues	Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree.	FOCS	1998	DBLP DOI BibTeX RDF	equational graphs, deterministic pushdown automata, rational languages, matrix semi-groups, complete formal systems, decidability, bisimulation
29	Fernando Rosa-Velardo, David de Frutos-Escrig	Decidability Results for Restricted Models of Petri Nets with Name Creation and Replication.	Petri Nets	2009	DBLP DOI BibTeX RDF
29	Matthias Horbach, Christoph Weidenbach	Decidability Results for Saturation-Based Model Building.	CADE	2009	DBLP DOI BibTeX RDF
29	Thomas Chatain, Paul Gastin, Nathalie Sznajder	Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems.	SOFSEM	2009	DBLP DOI BibTeX RDF	Distributed synthesis, Asynchronous systems
29	Jacques Sakarovitch, Rodrigo de Souza	On the Decidability of Bounded Valuedness for Transducers.	MFCS	2008	DBLP DOI BibTeX RDF
29	Marc Bezem, Tore Langholm, Michal Walicki	Completeness and Decidability in Sequence Logic.	LPAR	2007	DBLP DOI BibTeX RDF
29	Christopher Lynch, Duc-Khanh Tran	Automatic Decidability and Combinability Revisited.	CADE	2007	DBLP DOI BibTeX RDF
29	Agostino Dovier, Andrea Formisano 0001, Eugenio G. Omodeo	Decidability results for sets with atoms.	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	Prenex sentences, set-hyperset theories, syllogistics, unification, quantifier elimination, satisfiability problem
29	Riccardo Rosati 0001	On the decidability and finite controllability of query processing in databases with incomplete information.	PODS	2006	DBLP DOI BibTeX RDF
29	Maria Paola Bonacina, Silvio Ghilardi, Enrica Nicolini, Silvio Ranise, Daniele Zucchelli	Decidability and Undecidability Results for Nelson-Oppen and Rewrite-Based Decision Procedures.	IJCAR	2006	DBLP DOI BibTeX RDF
29	Rakesh M. Verma, Ara Hayrapetyan	A new decidability technique for ground term rewriting systems with applications.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	standard forms, unique normalization, decision procedures, rewriting, Confluence, pumping lemma
29	Michael Domaratzki, Kai Salomaa	Decidability of Trajectory-Based Equations.	MFCS	2004	DBLP DOI BibTeX RDF
29	Henning Bordihn, Markus Holzer 0001, Martin Kutrib	Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages.	CIAA	2004	DBLP DOI BibTeX RDF
29	Franz Baader, Silvio Ghilardi, Cesare Tinelli	A New Combination Procedure for the Word Problem That Generalizes Fusion Decidability Results in Modal Logics.	IJCAR	2004	DBLP DOI BibTeX RDF
29	Yasunori Ishihara, Yumi Shimakawa, Toru Fujiwara	Type Inferability and Decidability of the Security Problem Against Inference Attacks on Object-Oriented Databases.	ICICS	2004	DBLP DOI BibTeX RDF
29	Silvio Ghilardi, Luigi Santocanale	Algebraic and Model Theoretic Techniques for Fusion Decidability in Modal Logics.	LPAR	2003	DBLP DOI BibTeX RDF
29	Manfred Schmidt-Schauß	Decidability of Arity-Bounded Higher-Order Matching.	CADE	2003	DBLP DOI BibTeX RDF
29	Heinz Faßbender, Sebastian Maneth	A Strict Border for the Decidability of E-Unification for Recursive Functions.	ALP	1996	DBLP DOI BibTeX RDF
29	Salvatore Ruggieri	Decidability of Logic Program Semantics and Applications to Testing.	PLILP	1996	DBLP DOI BibTeX RDF
29	Parosh Aziz Abdulla, Mats Kindahl	Decidability of Simulation and Bisimulation between Lossy Channel Systems and Finite State Systems (Extended Abstract).	CONCUR	1995	DBLP DOI BibTeX RDF
29	Paritosh K. Pandya	Some Extensions to Propositional Mean-Value Caculus: Expressiveness and Decidability.	CSL	1995	DBLP DOI BibTeX RDF
29	Petr Jancar	Decidability Questions for Bismilarity of Petri Nets and Some Related Problems.	STACS	1994	DBLP DOI BibTeX RDF
29	Karel Culík II	New Techniques for Proving the Decidability of Equivalence Problems.	ICALP	1988	DBLP DOI BibTeX RDF
27	Giangiacomo Gerla	Decidability, partial decidability and sharpness relation for L-subsets.	Stud Logica	1987	DBLP DOI BibTeX RDF
24	Maria Bulinska	On the Complexity of Nonassociative Lambek Calculus with Unit.	Stud Logica	2009	DBLP DOI BibTeX RDF	Nonassociative Lambek calculus, P-TIME decidability, Context-free grammar
24	C. R. Prashanth, S. P. Ganavi, T. D. Mahalakshmi, K. B. Raja, K. R. Venugopal 0001, Lalit M. Patnaik	Iris feature extraction using directional filter bank for personal identification.	Bangalore Compute Conf.	2009	DBLP DOI BibTeX RDF	decidability index, directional filter bank, iris fragmentation, biometrics, iris recognition
24	Sergey Babenyshev, Vladimir V. Rybakov	Temporal Logic for Modeling Discovery and Logical Uncertainty.	KES (2)	2009	DBLP DOI BibTeX RDF	decidability algorithms, Kripke/Hintikka models, temporal logic, uncertainty, chance discovery
24	Gerardo Schneider	Reachability analysis of generalized polygonal hybrid systems.	SAC	2008	DBLP DOI BibTeX RDF	GSPDI, verification, hybrid systems, decidability, reachability
24	Vladimir V. Rybakov	Multi-agent Logics with Interacting Agents Based on Linear Temporal Logic: Deciding Algorithms.	ICAISC	2008	DBLP DOI BibTeX RDF	multi-agent logic, knowledge based reasoning, relational Kripke/Hintikka models, decidability algorithms, hybrid logics
24	Carsten Lutz, Maja Milicic	A Tableau Algorithm for Description Logics with Concrete Domains and General TBoxes.	J. Autom. Reason.	2007	DBLP DOI BibTeX RDF	concrete domains, tableau algorithm, description logic, decidability
24	Michael R. Hansen, Dang Van Hung	A Theory of Duration Calculus with Application.	Domain Modeling and the Duration Calculus	2007	DBLP DOI BibTeX RDF	metric-time temporal logic, Real-time systems, model-checking, application, decidability, duration calculus
24	Mikolaj Bojanczyk, Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin	Two-variable logic on data trees and XML reasoning.	PODS	2006	DBLP DOI BibTeX RDF	data trees, first-order logic, decidability
24	Andrzej Grzegorczyk	Undecidability without Arithmetization.	Stud Logica	2005	DBLP DOI BibTeX RDF	discernibility, Kurt Gödel, Alfred Tarski, representability, decidability, arithmetization, concatenation
24	Stefan S. Dantchev, Frank D. Valencia	On the computational limits of infinite satisfaction.	SAC	2005	DBLP DOI BibTeX RDF	infinite CSP, open CSP, decidability, constraint satisfaction problems
24	Luigi Di Lascio	Analytic fuzzy tableaux.	Soft Comput.	2001	DBLP DOI BibTeX RDF	Fuzzy deductive systems, Fuzzy logic, Completeness, Decidability, Soundness, Tableaux
24	Kosta Dosen, Zoran Petric	Coherent Bicartesian and Sesquicartesian Categories.	Proof Theory in Computer Science	2001	DBLP DOI BibTeX RDF	categorial proof theory, conjunction and disjunction, decidability of equality of deductions Mathematics Subject Classification (2000): 18A30, 18A15, 03G30, 03F05
24	Bartek Klin, Piotr Hoffman, Andrzej Tarlecki, Lutz Schröder, Till Mossakowski	Checking Amalgamability Conditions for C ASL Architectural Specifications.	MFCS	2001	DBLP DOI BibTeX RDF	formal specification and program development, CASL, algorithms, decidability, architectural specifications, amalgamation
24	Hsu-Chun Yen	Analysis of Self-Stabilization for Infinite-State Systems.	ICECCS	2001	DBLP DOI BibTeX RDF	Petri net, self-stabilization, Decidability, infinite-state system
24	Witold Charatonik, Andreas Podelski	Set Constraints with Intersection.	LICS	1997	DBLP DOI BibTeX RDF	satisfiability test, set-based program analysis, DEXPTIME-complete, complexity characterization, negative set constraints, negated conjuncts, negated inclusion, computability, decidability, intersection, inclusions, set constraints
23	Limin Jia 0001, Jianzhou Zhao, Vilhelm Sjöberg, Stephanie Weirich	Dependent types and program equivalence.	POPL	2010	DBLP DOI BibTeX RDF	dependent types, program equivalence
23	Jeremy E. Dawson, Alwen Tiu	Formalising Observer Theory for Environment-Sensitive Bisimulation.	TPHOLs	2009	DBLP DOI BibTeX RDF
23	Alwen Tiu, Rajeev Goré	A Proof Theoretic Analysis of Intruder Theories.	RTA	2009	DBLP DOI BibTeX RDF	AC convergent theories, intruder deduction, security protocols, sequent calculus
23	Guillem Godoy, Sebastian Maneth, Sophie Tison	Classes of Tree Homomorphisms with Decidable Preservation of Regularity.	FoSSaCS	2008	DBLP DOI BibTeX RDF
23	Carlos Olarte, Frank D. Valencia	The expressivity of universal timed CCP: undecidability of Monadic FLTL and closure operators for security.	PPDP	2008	DBLP DOI BibTeX RDF	first-order linear temporal logic, security protocols, closure operators, concurrent constraint programming
23	Riccardo Rosati 0001	On Combining Description Logic Ontologies and Nonrecursive Datalog Rules.	RR	2008	DBLP DOI BibTeX RDF
23	Mathilde Arnaud, Véronique Cortier, Stéphanie Delaune	Combining Algorithms for Deciding Knowledge in Security Protocols.	FroCoS	2007	DBLP DOI BibTeX RDF
23	Petr Jancar, Jirí Srba	Undecidability Results for Bisimilarity on Prefix Rewrite Systems.	FoSSaCS	2006	DBLP DOI BibTeX RDF
23	Nadia Busi	Deciding Behavioural Properties in Brane Calculi.	CMSB	2006	DBLP DOI BibTeX RDF
23	Piotr Hoffman	Unions of Equational Monadic Theories.	RTA	2006	DBLP DOI BibTeX RDF
23	Ullrich Hustadt, Boris Konev, Renate A. Schmidt	Deciding Monodic Fragments by Temporal Resolution.	CADE	2005	DBLP DOI BibTeX RDF
23	Piotr Hoffman	Union of Equational Theories: An Algebraic Approach.	RTA	2005	DBLP DOI BibTeX RDF
23	Laura Bozzelli	Model Checking for Process Rewrite Systems and a Class of Action-Based Regular Properties.	VMCAI	2005	DBLP DOI BibTeX RDF