java -Xss1g -Xmx8000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp18-benchmarks/lra/chc-lra-0085.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-20 23:02:26,942 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-20 23:02:26,944 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-20 23:02:26,957 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-20 23:02:26,958 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-20 23:02:26,959 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-20 23:02:26,960 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-20 23:02:26,964 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-20 23:02:26,965 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-20 23:02:26,967 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-20 23:02:26,968 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-20 23:02:26,968 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-20 23:02:26,969 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-20 23:02:26,969 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-20 23:02:26,973 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-20 23:02:26,973 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-20 23:02:26,975 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-20 23:02:26,984 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-20 23:02:26,985 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-20 23:02:26,986 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-20 23:02:26,987 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-20 23:02:26,991 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-20 23:02:26,991 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-20 23:02:26,992 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-20 23:02:26,992 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-20 23:02:26,993 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-20 23:02:26,995 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-20 23:02:26,996 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-20 23:02:26,997 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-20 23:02:26,997 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-20 23:02:26,997 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-20 23:02:26,998 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-20 23:02:26,998 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-20 23:02:26,999 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-20 23:02:27,000 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-20 23:02:27,000 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-20 23:02:27,013 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-20 23:02:27,013 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-20 23:02:27,013 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-20 23:02:27,013 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-20 23:02:27,015 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-20 23:02:27,015 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-20 23:02:27,015 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-20 23:02:27,015 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-20 23:02:27,015 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 23:02:27,015 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-20 23:02:27,016 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-20 23:02:27,016 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-20 23:02:27,016 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-20 23:02:27,016 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-20 23:02:27,016 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-20 23:02:27,016 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-20 23:02:27,017 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-20 23:02:27,018 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-20 23:02:27,018 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-20 23:02:27,068 INFO ]: Repository-Root is: /tmp [2018-06-20 23:02:27,084 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-20 23:02:27,091 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-20 23:02:27,093 INFO ]: Initializing SmtParser... [2018-06-20 23:02:27,093 INFO ]: SmtParser initialized [2018-06-20 23:02:27,093 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp18-benchmarks/lra/chc-lra-0085.smt2 [2018-06-20 23:02:27,095 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-20 23:02:27,181 INFO ]: Executing SMT file /storage/chc-comp18-benchmarks/lra/chc-lra-0085.smt2 unknown [2018-06-20 23:02:27,651 INFO ]: Succesfully executed SMT file /storage/chc-comp18-benchmarks/lra/chc-lra-0085.smt2 [2018-06-20 23:02:27,656 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-20 23:02:27,661 INFO ]: Walking toolchain with 4 elements. [2018-06-20 23:02:27,662 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-20 23:02:27,662 INFO ]: Initializing ChcToBoogie... [2018-06-20 23:02:27,662 INFO ]: ChcToBoogie initialized [2018-06-20 23:02:27,665 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,782 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27 Unit [2018-06-20 23:02:27,782 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-20 23:02:27,783 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-20 23:02:27,783 INFO ]: Initializing Boogie Preprocessor... [2018-06-20 23:02:27,783 INFO ]: Boogie Preprocessor initialized [2018-06-20 23:02:27,815 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,824 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,845 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,845 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,881 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,883 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,888 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... [2018-06-20 23:02:27,901 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-20 23:02:27,902 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-20 23:02:27,902 INFO ]: Initializing RCFGBuilder... [2018-06-20 23:02:27,902 INFO ]: RCFGBuilder initialized [2018-06-20 23:02:27,903 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-20 23:02:27,931 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-20 23:02:27,931 INFO ]: Found specification of procedure gotoProc [2018-06-20 23:02:27,931 INFO ]: Found implementation of procedure gotoProc [2018-06-20 23:02:27,931 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-20 23:02:27,931 INFO ]: Found specification of procedure Ultimate.START [2018-06-20 23:02:27,931 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 23:02:28,347 INFO ]: Using library mode [2018-06-20 23:02:28,348 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 11:02:28 BoogieIcfgContainer [2018-06-20 23:02:28,348 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-20 23:02:28,349 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-20 23:02:28,349 INFO ]: Initializing TraceAbstraction... [2018-06-20 23:02:28,357 INFO ]: TraceAbstraction initialized [2018-06-20 23:02:28,357 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 11:02:27" (1/3) ... [2018-06-20 23:02:28,358 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65c5c4e0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 20.06 11:02:28, skipping insertion in model container [2018-06-20 23:02:28,358 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 11:02:27" (2/3) ... [2018-06-20 23:02:28,358 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65c5c4e0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.06 11:02:28, skipping insertion in model container [2018-06-20 23:02:28,358 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 11:02:28" (3/3) ... [2018-06-20 23:02:28,360 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-20 23:02:28,369 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-20 23:02:28,377 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-20 23:02:28,427 INFO ]: Using default assertion order modulation [2018-06-20 23:02:28,428 INFO ]: Interprodecural is true [2018-06-20 23:02:28,428 INFO ]: Hoare is false [2018-06-20 23:02:28,428 INFO ]: Compute interpolants for FPandBP [2018-06-20 23:02:28,428 INFO ]: Backedges is TWOTRACK [2018-06-20 23:02:28,428 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-20 23:02:28,428 INFO ]: Difference is false [2018-06-20 23:02:28,428 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-20 23:02:28,428 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-20 23:02:28,441 INFO ]: Start isEmpty. Operand 10 states. [2018-06-20 23:02:28,455 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-20 23:02:28,455 INFO ]: Found error trace [2018-06-20 23:02:28,456 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:02:28,456 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:02:28,461 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-20 23:02:28,463 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:02:28,464 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:02:28,495 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:28,495 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:02:28,495 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:28,562 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:28,711 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:28,714 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-20 23:02:28,714 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-20 23:02:28,716 INFO ]: Interpolant automaton has 3 states [2018-06-20 23:02:28,732 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-20 23:02:28,733 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-20 23:02:28,736 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-20 23:02:28,826 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:02:28,826 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-20 23:02:28,827 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-20 23:02:28,828 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-20 23:02:28,828 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:02:28,839 INFO ]: With dead ends: 9 [2018-06-20 23:02:28,839 INFO ]: Without dead ends: 9 [2018-06-20 23:02:28,841 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-20 23:02:28,878 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-20 23:02:28,904 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-20 23:02:28,905 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-20 23:02:28,905 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-20 23:02:28,907 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-20 23:02:28,907 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:02:28,907 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-20 23:02:28,907 INFO ]: Interpolant automaton has 3 states. [2018-06-20 23:02:28,907 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-20 23:02:28,907 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-20 23:02:28,908 INFO ]: Found error trace [2018-06-20 23:02:28,908 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:02:28,908 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:02:28,908 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-20 23:02:28,908 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:02:28,908 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:02:28,909 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:28,909 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:02:28,909 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:29,064 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:29,379 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:29,379 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:02:29,379 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-20 23:02:29,395 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:02:29,538 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:29,553 INFO ]: Computing forward predicates... [2018-06-20 23:02:30,283 WARN ]: Spent 165.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-20 23:02:30,300 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:30,338 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:02:30,338 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-20 23:02:30,338 INFO ]: Interpolant automaton has 6 states [2018-06-20 23:02:30,339 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-20 23:02:30,339 INFO ]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-20 23:02:30,339 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-20 23:02:30,590 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:02:30,590 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-20 23:02:30,591 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-20 23:02:30,591 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-20 23:02:30,591 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:02:30,591 INFO ]: With dead ends: 11 [2018-06-20 23:02:30,591 INFO ]: Without dead ends: 11 [2018-06-20 23:02:30,592 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-20 23:02:30,592 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-20 23:02:30,593 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-20 23:02:30,594 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-20 23:02:30,594 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-20 23:02:30,594 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-20 23:02:30,594 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:02:30,594 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-20 23:02:30,594 INFO ]: Interpolant automaton has 6 states. [2018-06-20 23:02:30,594 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-20 23:02:30,594 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-20 23:02:30,594 INFO ]: Found error trace [2018-06-20 23:02:30,595 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:02:30,595 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:02:30,595 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-20 23:02:30,595 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:02:30,595 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:02:30,596 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:30,596 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 23:02:30,596 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:30,853 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:31,304 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 3 [2018-06-20 23:02:31,484 WARN ]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-20 23:02:31,494 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:31,494 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:02:31,494 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:02:31,501 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-20 23:02:31,677 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-20 23:02:31,677 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:31,688 INFO ]: Computing forward predicates... [2018-06-20 23:02:33,227 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:33,249 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:02:33,249 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-20 23:02:33,249 INFO ]: Interpolant automaton has 10 states [2018-06-20 23:02:33,249 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-20 23:02:33,249 INFO ]: CoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-06-20 23:02:33,250 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-06-20 23:02:33,459 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:02:33,459 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-20 23:02:33,459 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-20 23:02:33,459 INFO ]: Start accepts. Automaton has 10 states. Word has length 10 [2018-06-20 23:02:33,459 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:02:33,459 INFO ]: With dead ends: 12 [2018-06-20 23:02:33,459 INFO ]: Without dead ends: 12 [2018-06-20 23:02:33,460 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=55, Invalid=101, Unknown=0, NotChecked=0, Total=156 [2018-06-20 23:02:33,460 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-20 23:02:33,462 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-20 23:02:33,462 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-20 23:02:33,462 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-20 23:02:33,462 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-20 23:02:33,462 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:02:33,462 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-20 23:02:33,462 INFO ]: Interpolant automaton has 10 states. [2018-06-20 23:02:33,463 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-20 23:02:33,463 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-20 23:02:33,463 INFO ]: Found error trace [2018-06-20 23:02:33,463 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:02:33,463 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:02:33,463 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 3 times [2018-06-20 23:02:33,463 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:02:33,463 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:02:33,464 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:33,464 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:02:33,464 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:33,596 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:34,179 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 3 [2018-06-20 23:02:34,798 WARN ]: Spent 359.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 13 [2018-06-20 23:02:34,866 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:34,867 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:02:34,867 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:02:34,875 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-20 23:02:35,016 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-20 23:02:35,016 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:35,030 INFO ]: Computing forward predicates... [2018-06-20 23:02:38,548 WARN ]: Spent 757.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 20 [2018-06-20 23:02:39,028 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:39,049 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 23:02:39,049 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-20 23:02:39,050 INFO ]: Interpolant automaton has 12 states [2018-06-20 23:02:39,050 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-20 23:02:39,050 INFO ]: CoverageRelationStatistics Valid=40, Invalid=92, Unknown=0, NotChecked=0, Total=132 [2018-06-20 23:02:39,050 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-06-20 23:02:39,495 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 23:02:39,495 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-20 23:02:39,496 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-20 23:02:39,496 INFO ]: Start accepts. Automaton has 12 states. Word has length 11 [2018-06-20 23:02:39,496 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 23:02:39,496 INFO ]: With dead ends: 15 [2018-06-20 23:02:39,496 INFO ]: Without dead ends: 15 [2018-06-20 23:02:39,497 INFO ]: 0 DeclaredPredicates, 23 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=103, Invalid=203, Unknown=0, NotChecked=0, Total=306 [2018-06-20 23:02:39,497 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-20 23:02:39,498 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-20 23:02:39,498 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-20 23:02:39,499 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-20 23:02:39,499 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 11 [2018-06-20 23:02:39,499 INFO ]: Finished accepts. word is rejected. [2018-06-20 23:02:39,499 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-20 23:02:39,499 INFO ]: Interpolant automaton has 12 states. [2018-06-20 23:02:39,499 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-20 23:02:39,499 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-20 23:02:39,499 INFO ]: Found error trace [2018-06-20 23:02:39,499 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 23:02:39,499 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 23:02:39,499 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 4 times [2018-06-20 23:02:39,499 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 23:02:39,499 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 23:02:39,500 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:39,500 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 23:02:39,500 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 23:02:39,812 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:40,555 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 23:02:40,555 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 23:02:40,555 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:02:40,598 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-20 23:02:40,867 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-20 23:02:40,867 INFO ]: Conjunction of SSA is unsat [2018-06-20 23:02:40,884 INFO ]: Computing forward predicates... [2018-06-20 23:02:41,513 WARN ]: Spent 205.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-20 23:02:43,188 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 114 DAG size of output: 25 [2018-06-20 23:02:46,830 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 26 Received shutdown request... [2018-06-20 23:03:30,751 WARN ]: Removed 166 from assertion stack [2018-06-20 23:03:30,754 INFO ]: Timeout while computing interpolants [2018-06-20 23:03:30,955 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 23:03:30,955 WARN ]: Verification canceled [2018-06-20 23:03:30,959 WARN ]: Timeout [2018-06-20 23:03:30,960 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.06 11:03:30 BoogieIcfgContainer [2018-06-20 23:03:30,960 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-20 23:03:30,960 INFO ]: Toolchain (without parser) took 63304.20 ms. Allocated memory was 305.7 MB in the beginning and 2.6 GB in the end (delta: 2.3 GB). Free memory was 242.1 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 2.4 GB. Max. memory is 7.1 GB. [2018-06-20 23:03:30,961 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.7 MB. Free memory is still 269.2 MB. There was no memory consumed. Max. memory is 7.1 GB. [2018-06-20 23:03:30,961 INFO ]: ChcToBoogie took 120.47 ms. Allocated memory is still 305.7 MB. Free memory was 241.1 MB in the beginning and 238.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 7.1 GB. [2018-06-20 23:03:30,962 INFO ]: Boogie Preprocessor took 118.83 ms. Allocated memory is still 305.7 MB. Free memory was 238.1 MB in the beginning and 236.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. [2018-06-20 23:03:30,962 INFO ]: RCFGBuilder took 445.75 ms. Allocated memory is still 305.7 MB. Free memory was 236.1 MB in the beginning and 203.9 MB in the end (delta: 32.3 MB). Peak memory consumption was 32.3 MB. Max. memory is 7.1 GB. [2018-06-20 23:03:30,963 INFO ]: TraceAbstraction took 62610.34 ms. Allocated memory was 305.7 MB in the beginning and 2.6 GB in the end (delta: 2.3 GB). Free memory was 202.9 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 2.3 GB. Max. memory is 7.1 GB. [2018-06-20 23:03:30,966 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 305.7 MB. Free memory is still 269.2 MB. There was no memory consumed. Max. memory is 7.1 GB. * ChcToBoogie took 120.47 ms. Allocated memory is still 305.7 MB. Free memory was 241.1 MB in the beginning and 238.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 118.83 ms. Allocated memory is still 305.7 MB. Free memory was 238.1 MB in the beginning and 236.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. * RCFGBuilder took 445.75 ms. Allocated memory is still 305.7 MB. Free memory was 236.1 MB in the beginning and 203.9 MB in the end (delta: 32.3 MB). Peak memory consumption was 32.3 MB. Max. memory is 7.1 GB. * TraceAbstraction took 62610.34 ms. Allocated memory was 305.7 MB in the beginning and 2.6 GB in the end (delta: 2.3 GB). Free memory was 202.9 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 2.3 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 15 with TraceHistMax 7, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 801. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 62.5s OverallTime, 5 OverallIterations, 7 TraceHistogramMax, 1.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 3 SDslu, 89 SDs, 0 SdLazy, 39 SolverSat, 18 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 57 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 3.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred in iteration=4, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 8.6s InterpolantComputationTime, 65 NumberOfCodeBlocks, 65 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 58 ConstructedInterpolants, 0 QuantifiedInterpolants, 1943 SizeOfPredicates, 8 NumberOfNonLiveVariables, 1305 ConjunctsInSsa, 51 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/34 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lra-0085.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-20_23-03-30-980.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lra-0085.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-20_23-03-30-980.csv Completed graceful shutdown